时间限制：1s，空间限制：256mb

问题描述

远坂凛与卫宫士郎遭遇了caster召唤的龙牙兵的袭击，每个龙牙兵拥有生命值L[i]与防御力f[i]。
远坂凛一共拥有m种类型的宝石攻击魔法，第i种魔法，需要消耗k[i]个宝石，并对怪兽造成g[i]点伤害。卫宫士郎只会物理攻击。
当然，如果远坂凛使用第i种魔法攻击第j个龙牙兵的话，会使得第j个龙牙兵的生命值减少g[i]-f[j]，所以当攻击伤害小于防御力时，魔法就不会有效果。而卫宫士郎的物理攻击可以无视龙牙兵的防御力，但每消灭一个龙牙兵，会损失t[j]点体力值。
如果魔法攻击使龙牙兵j的生命值L[j]≤ 0或者卫宫士郎花费t[j]点体力值，那么龙牙兵j就会被消灭。
若卫宫士郎的体力值为w，他一开始尽可能地消灭龙牙兵，然后远坂凛施法消灭剩下的龙牙兵。
若每种魔法都可以使用无限次，请问远坂凛最少携带多少宝石，就可以消灭剩下的龙牙兵。

输入格式

从文件fsn.in中输入数据。
第一行两个整数n，m，w表示有n个龙牙兵，m种魔法，w点体力值。
接下来n行，每行两个整数，L[i]，f[i]，t[i]分别表示龙牙兵的生命值和防御力,以及物理杀死这个龙牙兵所需的体力值。
再接下来m行，每行两个整数k[i]和g[i]，分别表示这种魔法消耗宝石数目和伤害值。

输出格式

输出到文件fsn.out中。
输出一行，一个整数表示最小的宝石消耗数量。

样例输入

1 2 5
4 5 4
10 7
9 6

样例输出

0

数据规模与约定

对于10%的数据，1 ≤ n ≤ 100,1 ≤ m ≤ 50,1 ≤ w ≤ 50,
对于50%的数据，1 ≤ n≤ 500,1 ≤ m≤ 100,w<=50,1 ≤ L[i] ≤ 200,0 ≤ f[i]≤ 10,0 ≤ t[i]≤ 20,0 ≤ k[i] ≤ 100,0 ≤ g[i] ≤ 100，
对于100%的数据，1 ≤ n ≤ 3000,1 ≤ m≤ 2000,w<=2000,1≤ L[i]≤ 1000,0≤ f[i]≤ 10,0≤ t[i]≤ 300,0≤ k[i]≤ 100000,0≤ g[i]≤ 1000。