T457604 老八秘制小汉堡~~

众所周知，老八是一个厨师，现在，他在做饭，突然，他想到了一个奇妙的问题~~（注：本题时限 $5s$）

有 $n$ 位客人，第 $i$ 位客人的饱和度需求为 $a_i$。老八的合伙人有 $m$ 种食物，每种食物有三个数值：$w_i$，$v_i$，$s_i$。其中 $w_i$ 表示食物的饱和度，$v_i$ 表示食物需要的价格，$s_i$ 表示每次买了一次食物时物价上涨了多少（可以为 $0$），老八想知道要满足所有的客人，至少要用几块钱？（即第 $i$ 种食物购买了 $k$ 次后，价格加上 $k\times s_i$）

第 $1$ 行，一个整数，表示 $n$。 第 $2$ 行，$n$ 个整数，表示 $a_i$。 第 $3$ 行，一个整数，表示 $m$。 第 $4$ 到 $3 + m$ 行，每行 $3$ 个整数，表示 $w_i,v_i,s_i$。

一行，一个整数 $minn$，表示最小价值。

$10\%$ 的数据，$0 < n,m < 6$。 $50\%$ 的数据，$0 < n,m < 21$。 $100\%$ 的数据，$0 < n,m < 10^4 + 1$。 $a_i,w_i,v_i,s_i$ 均小于 $10^3 + 1$。 $\sum a_i\le 5\times 10^3 $。