小邱是小西的朋友，听到小西用最少的价格买到了口罩，决定自己出去买口罩，但是小邱的数二崩了，所以算数很差，他请你来帮忙，并且小邱不敢购买一盒超过x个口罩的包装盒,他觉得一盒超过x个口罩就是假的，如果买的这盒口罩超过x个，那小邱就再也不会购买这种盒装口罩。 “老板你这口罩怎么卖？” “我这里有m种盒装口罩，a[i]元一盒有b[i]个口罩，正版N99口罩，童叟无欺” “老板，你怎么卖口罩，还兼职弹手风琴卖艺呀” “因为，没人比我更懂口罩” “可是，你这价格？感觉好奇怪呀。” “shut up！nobody knows masks better than me。不买就一边去。” “好吧好吧，我至少买n个”
输入描述:
输入第一行包含两个整数n,m(1<=n,m<=1000)，表示至少需要买n个口罩，m种包装。
接下来m行，每行包括两个数a[i],b[i]（0<a[i]<=100,0<b[i]<=10000），意思a[i]元一盒含有b[i]个口罩的包装。
下面一行是一个整数k(1<=k<=2e5)，意思有k次不同x值的询问
紧接着是k行，每一行包含一个整数x(0<x<=10000)。
输出描述:
对于最后k行，对应每一行的整数x，需要输出一个值表示至少买n个最小花费的钱数。
如果买不到至少n个口罩，则输出-1。
示例1
输入
复制
3 3
1 200
2 300
3 400
3
2
3
4