21777_addHP

最近小白迷上了剑侠情缘，可惜不幸的是他千挑万选拜入了一个叫做"万花"的门派。事实上，这个门派的主要作用就是在别人受到伤害的时候，施展技能使得好友的生命值得以恢复。

可是万花的技能有一个缺陷，那就是玩家所谓的读条。

读条就是一个技能的施法时间，也就是说当我按下一个技能的操作之后，这个技能会在S秒之后才会被释放出来。

万花拥有数个加血技能，它们的施法时间和加血量也不尽相同。现在小白和大家一起去下副本，责任当然是负责照顾好MT（Main Tank）。根据小白多年来的经验，可以推算出BOSS每一次攻击对MT造成的伤害，小白希望你帮忙算一下MT是否能够存活下来，如果可以，那么怎么加血，才能使得MT的最低血量最高？（MT的血量一旦太低，会导致大家的惊恐，所以小白希望知道怎么加血才能让MT曾经被打击造成的血量最低值尽可能高一些）。

第一行输入三个数字 n，m和HP，n 代表BOSS的攻击次数，m代表万花的加血技能有多少个，HP代表MT初始状态下有多少血（此时HP为MT的上限）。

接下去n个数字，第i个数字代表BOSS在第i秒对MT造成多少伤害。

接下去m行数字，每行输入一个time和一个add；

time代表技能如果在k时间开始读条，那么会在k + time时间完成效果

add代表该技能可以恢复多少HP，但不允许超过MT的上限。

由于我们会偷袭BOSS，所以可以看做从0时间开始加血，而BOSS的伤害从1时间点才开始计算，但是BOSS得伤害会在加血技能之前被计算。

0 ≤ n, m ≤ 10000 ，0 ≤ HP, time , add ≤ 1000 ,

如果MT能存活，则输出MT的到达过的最小血量，否则输出"Die"。

10 2 100
1 1 1 1 1 1 1 1 1 1
2 10
1 1

99