故事发生在公元118年。

题目背景

家鸡帝国在休养生息了两年半后准备去...
做什么呢？
什么呢？
家鸡会做什么呢？(也许呢)
究竟是什么呢？
到底是什么？
什么？
什么？？
什么？？？
什么？！
什么！
当然是开贸易路线啦！
哔~~~~~~~(手动混音)

不管怎么说，他还是决定开贸易路线。

题目描述

家鸡目前已知有 \(n\) 个他国城市愿意跟他开贸易路线并将他们从1到 \(n\) 排了序。(贸易路线只能跟他国城市开)，且他最多能开 \(m\) 条贸易路线 而与编号为 \(i\) 的城市开贸易路线能增加 \(a_i\) 经济，但是一个本国城市不能跟任意一个城市开两条贸易路线。家鸡的被编号为从1到 \(k\) 的 \(k\) 个城市中编号为 \(i\) 个城市可以跟 \(c_i\) 个他国城市开贸易路线，并原有 \(t_i\) 点经济。

现在，他让你求出经济最差的一个城市经济最好是多少？

输入数据

第一行，是 \(n\) , \(m\) , \(k\) 。
第二行， \(n\) 个数字，第 \(i\) 个数指 \(a_i\) 。
第三到 \(k+2\) 行，每行 \(2+c_i\) 个数，分别是 \(t_i\) , \(c_i\) ,接下来 \(c_i\) 个数是能与第几个城市开贸易路线。

sample1

5 3 5
5 6 5 4 5
10 1 4
20 1 2
10 1 4
10 1 4
20 5 1 2 3 4 5

sample 2

1 10 5
1
1 1 1
1 1 1
1 1 1
1 1 1
114 1 1

输出样例

共一行，一个整数，指经济最差的一个城市经济最好是多少。

sample1

14

sample2

2

数据范围

\(n,k<=2000|m<=100|a_i<=100|t_i<=10000\)