宝石商人

题目描述

璀璨宝石是一个经典桌游， 在璀璨宝石中，玩家将回到文艺复兴时期，成为一位宝石富商。现在已知有n种类型宝石，每个宝石你拥有 $a_i$ 个。有 $m$ 个矿藏，每个矿藏有 $v_i$ 点价值。每个矿藏需要花费 $n$ 种宝石，每种 $b_i$($1<=i<=n, b_i>=0$)表示第 $i$ 种宝石需要花费的数量( $b_i$ 不全为0)。

现在求你最大能获得的矿藏价值 $v_i$ 的总和。

输入描述

第一行 $n \ m$，表示宝石总数和矿藏总数。

第二行 $n$ 个数 $a_i$，表示每种宝石的拥有量。

接下来 $2*m$ 行，每两行第一行 $v$ 和第二行 $b_i$，表示矿藏价值和每种宝石需要的花费的量。

输出描述

一个整数，最大矿藏价值总和

输入样例

5 4
1 2 3 4 5
10
1 0 0 0 1
20
0 2 3 1 4
10
0 2 3 4 4
999
2 0 0 0 0

输出样例

30

数据范围

n<=20

$m*a_1*a_2* a_3*…*a_n<=10^7$

$a_1*a_2* a_3*…*a_n<=10^5$

保证v和答案不超过int的范围