题目内容

临近双十一，小明打算采买一批货物。其中 $a$ 件属于非买不可，另外 $b$ 件是可加可不加的凑单货。他手里同时还攥着 $c$ 张券，每一张都标明了种类（减钱或者打折）以及启用条件。请算出小明把账结清时，实际掏出的钱最少能压到多少。

规则说明：

1、货物怎么买：

• 凡是非买不可的货，都要一件不落地全部拿下。
• 凑单货由你决定放进或不放进购物车，同一件至多放进一次。

2、券怎么启用：

• 每一张券至多启用一次，也可以整张弃用。
• 启用的先后允许自行排列，应当找出让实付最小的那种次序。
• 每张券带一个启用条件 $g$（正整数）。意思是，套用它的前一刻，订单现价得满足 $\geq g$，不然这张就不能套用。

3、券分成哪两类：

• $f = 0$：减钱券。套用之后，把现价立刻扣掉 $d$（正整数）。
• $f = 1$：打折券。套用之后，现价改写成 $\text{floor}(\text{现价} \times d / 100)$，也就是把小数直接舍掉。
• 注意：一张券生效完毕，算出来的新现价，会变成后面其余券的对照基准。

输入描述

第一行给出三个整数 $a$、$b$、$c$（$1 \le a \le 10$，$0 \le b \le 10$，$0 \le c \le 5$）。

紧随其后单独一行，写下 $a$ 个整数，依次是非买不可那些货的标价（单个标价 $\le 1000$）。

再往后一行，写下 $b$ 个整数，依次是凑单货的标价（单个标价 $\le 1000$）。当 $b = 0$ 时，这一行直接省掉。

最后还有 $c$ 行，每一行对应一张券，书写次序是 $f$、$g$、$d$。

$f$ 只允许取 $0$ 或者 $1$。

$g$ 和 $d$ 都得是正整数（若该券属于打折，则 $d$ 代表折扣比例，比如写 $80$ 就是按八折计）。

输出描述

交出一行，里面只放一个整数，代表结账最少要掏的钱。

补充说明

提示

1、要是全部选定的券都套完后，现价掉成了负数，交卷时改记成 $0$。

样例1

输入

2 1 2
80 40
30
0 150 40
1 100 80

输出

88

说明

只拿非买不可的两件，标价相加是 $80 + 40 = 120$。减钱券要现价至少 $150$，此刻用不上；打折券可以套，$120 \times 80 / 100 = 96$。

把标价 $30$ 的凑单货也放进去，现价变成 $150$。先扣掉 $40$ 得到 $110$，再按八折得到 $\lfloor 110 \times 80 / 100 \rfloor = 88$。若先打八折得到 $120$，就够不着减钱券的条件，实付停在 $120$。只扣不折是 $110$，只折不扣是 $120$。这几种结法里最小的是 $88$。

样例2

输入

2 1 2
60 40
20
0 100 30
1 80 50

输出

45

说明

非买不可的两件合计 $60 + 40 = 100$。这时先按五折计算得到 $50$，减钱券的条件就达不到；先扣掉 $30$ 得到 $70$，五折券要求现价至少 $80$，同样套不上。所以只拿这些必买货，最好是 $50$。

再放入标价 $20$ 的凑单货，现价升到 $120$。先扣掉 $30$ 得到 $90$，接着按五折得到 $\lfloor 90 \times 50 / 100 \rfloor = 45$。先按五折会得到 $60$，减钱券要求的 $100$ 够不着。因此实付最少是 $45$。