### 问题描述 小蓝今天兴致勃勃地去商场逛街，他心里已经有了一份购物清单，准备购买 $n$ 个物品。然而，他知道节省每一分钱都很重要，所以他带着 $m$ 种不同类型的优惠券，第 $i$ 种优惠券共有 $s_i$ 张。 每个物品都有一个价格 $p_i$，而小蓝手上的优惠券则分为两种类型：减满券和折扣券。对于第 $i$ 种优惠券，它可以减少小蓝购买某件物品的价格。如果是减满券，则某件物品金额大于等于 $A_i$ 元时，该物品可以减少 $B_i$ 元的支付金额；如果是折扣券，则可以享受 $X_i$ 折的优惠，即折后价格为 $\lceil \frac{p_i \times X_i}{100} \rceil$。 小蓝可以随意安排优惠券的使用，但每种物品只能使用一张优惠券，并且每张优惠券只能使用一次。请问小蓝最少需要付多少钱。 $\lceil \rceil$ 符号代表向上取整，例如 $\lceil 1.5 \rceil = 2,\lceil 2 \rceil = 2 $。 ### 输入格式 第一行包含两个整数 $n$ 和 $m$，分别表示物品的数量和优惠券的种类数。$1 \le n, m \le 200$。 接下来一行包含 $n$ 个整数，表示每个物品的价格 $p_i$。$1 \le p_i \le 10^5$，单位为元。 接下来 $m$ 行，每行描述一种优惠券。包含 $3$ 个整数，$s_i, A_i, B_i/X_i$，代表该类优惠券数量是 $s_i$ 张，$B_i/X_i$ 代表输入是 $B_i$ 或者是 $X_i$，具体取决于 $A_i$ 的值： 1. 如果 $A_i$ 为 $0$，代表是折扣券，折扣为 $X_i$。 2. 如果 $A_i$ 不为 $0$，代表是减满券，购物金额达到 $A_i$ 元后，可以减少 $B_i$ 元。 $1 \le s_i \le n$，当 $A_i = 0$ 时，$1 \le X_i \le 100$，否则 $1 \le B_i \le A_i \le 10^5$。 ### 输出格式 输出一个整数，表示小蓝最少需要付多少钱。 ### 样例输入 ```plaintext 3 2 10 20 30 1 10 5 2 0 50 ``` ### 样例输出 ```plaintext 30 ``` ### 说明 在这个样例中，小蓝购买的第一个物品价格为 $10$，第二个物品价格为 $20$，第三个物品价格为 $30$。 他可以选择使用第一种优惠券，将第一个物品的价格减少 $5$ 元，第二、三个物品使用折扣券，打 $50\\%$ 的折扣，最后的总价为 $10 - 5 + (30 + 20) \times 50\\% = 30$ 元。