U177647 LBW买东西

LBW买东西 有的人问，为什么不是lbw去买 因为lbw正在斗地主，只能让他的好大儿LBW去

LBW去买东西的超市有 $m$ 种促销的方式 每一种促销的方式可以简化为 $f$，$a$，$q$，表示如果你有第 $f$ 种物品和 $a$ 元钱，那你就能换取第 $q$ 种物品 因为Rir5AKIOI，所以LBW能够随便挑一个物品无限拿 现在LBW想知道，在买到全 $n$ 种物品后，最少花多少钱

第一行两个整数 $n$,$m$ ，表示物品数和优惠条数 第二行 $n$ 个整数，第 $i$ 个整数表示直接买第 $i$ 个物品花多少钱 后面 $m$ 行，每行三个整数 $f$,$a$,$q$,描述一条优惠

一个整数，在买到全 $n$ 个物品后最少花多少钱

保证LBW不可能用他换到的东西换他当前的东西，换句话说，不可能存在说我用物品 $a$ 换到了物品 $b$ 而物品 $b$ 又能通过一些操作换到物品 $a$ 你能看到的所有数，不超过 $100000$ 样例解释： 选择物品 $1$ 免费，后可以用这个物品各加1块钱换到物品 $2$ 和物品 $3$，所以是 $2$ 块钱