国王在他的国家发现了座金矿，为了描述方便，我们给他们从1到编号。
对于第个金矿，需要投入个的费用，能挖出来个单位的金子。
现在国王想开挖这些金矿，但是最多只有个软妹币用于投入，问最多可以挖出来多少单位的金子。
第一行两个整数，分别为和。
接下来 行每行两个整数，第行为和。
一行一个整数，为最多可以挖出来多少单位的金子。
3 10 8 5 3 4 6 3
7
1 , 2000
1 300000