Joshua的炉石狂想

题目描述

最近Joshua沉迷炉石，但是作为公关部之星，常常被事务（撩妹）缠身导致没法专心致志，老是没法打出最好的套路，现在他新组建了一套强力的冲锋卡组（所有的角色召唤出来即可进行攻击），无奈对方是嘲讽卡组十分讨厌。

在这个新的回合，Joshua又获得了x个水晶（水晶足够才能进行召唤）并且y张手牌有y只“强力“的冲锋怪，Joshua很忙，只能甩锅给你们来计算出这回合能对对方英雄造成的最大伤害了。

Hint

1. 双方场上最多有7只怪。
2. 如果对方场上有嘲讽怪存在的话是无法攻击到英雄的（这个时候攻击嘲讽怪就好了）。
3. 每只怪每回合只能攻击一次，且刚开始Joshua场上没有怪。
4. Joshua比较懒，只想在召唤结束后就进行攻击，然后结束回合。

输入

第一行 有三个数字x，y，z

接下来y行每行有2个数字m，n，m表示手牌中这只怪的攻击力，n表示召唤这只怪所需的水晶数。

接下来z行每行有1个数字表示对手嘲讽怪的血量值hp。

$0 \leq x \leq 10$

$0 \leq y \leq 10$

$0 \leq z \leq 7$

$0 \leq m \leq 20$

$0 \leq n \leq 20$

$0 < hp \leq 20$

输出

输出一行——能够对对方英雄造成的最大伤害值。

输入样例

6 2 1
3 3
4 3
1

输出样例

4