Olivia 经营着一家非常著名且盈利的奶昔摊。在任何一天，她总是能卖光所有的奶昔（也就是说，她能卖出多少奶昔就卖出多少，取决于她拥有的配料量），无论她提供哪种奶昔配方。因此，为了简化问题，她决定每天只制作一种奶昔。现在她来找你帮忙，根据她手头现有的配料以及每种奶昔的售价，决定今天应该使用哪种配方。

输入格式

第一行包含两个整数 $k$ 和 $r$，中间用空格隔开。$k$ 是 Olivia 制作奶昔所使用的不同配料的数量，$r$ 是她拥有的不同配方数量。你可以假设 $1 \leq k \leq 100\,000$，$1\leq r\leq 100\,000$，且 $1 \leq kr \leq 100\,000$。第二行包含 $k$ 个整数，表示她目前手头拥有的每种配料的数量。接下来有 $r$ 行，每一行代表一个配方。在每一行中，前 $k$ 个用空格隔开的整数表示该配方中每种配料的使用量。随后是一个整数，表示该配方制作一份奶昔的售价。

你可以假设除 $k$ 和 $r$ 外，所有数值均为小于或等于 $10^4$ 的非负整数。保证每个配方至少使用一种配料。

输出格式

输出通过选择单一配方并尽可能多地制作该配方所能获得的最大总销售收入。

样例

样例输入 1

3 2
5 10 10
1 4 1 5
3 3 3 3

样例输出 1

10

样例输入 2

4 3
10 9 8 7
0 1 2 4 10
3 1 1 2 4
2 0 3 3 5

样例输出 2

12