Edward's Cola Plan

Time Limit: 3 Seconds
Memory Limit: 32768 KB

*Edward* is a tall, handsome and rich (a.k.a *GaoShuaiFu*, *GSF*) student who studys in Zhejiang University.
He also takes part in many competition of *ACM-ICPC*, and he is so smart that he almost wins the championship of *World Finals* recently!
Unfortunately, he doesn't spent time in studying, so when the result of the final examination is published, he finds that he can't pass *Mathematical Analysis*! What a sad thing it is!
But luckily, he still pass *General Physics*, so he decides to treat
his `N` friends some *Coca-Cola*. The *Coca-Cola* is cheap - it only costs 3 yuan to buy one bottle.

What's more, he knows that the Cola company is holding a promotional activity
again that customers can exchange one bottle of cola with `M` caps. And, because his friends are all good guys, they will give him some caps after drinking the Cola.
After he deliberate for a long time, he thinks exactly one *Coca-Cola* for each person is enough. He is so happy!

But it's not so easy. The Cola company prints some signs on the Cola which is exchanged by caps, such as "Free!", "Gifts!", "Let's black someone!", and so on. We can call it *Gift Cola*.
His friends have different attitude toward to different Cola. To more specific, if *Edward* gives the `i`^{th} friend a bottle of *Normal Cola*, he can get `Pi` caps back; and if he gives a bottle of *Gift Cola*, he can get `Qi` caps back.

*Edward* loves caps and he wants to get the most caps he can! However, the Cola Company often changes the variable `M`. So *Edward* asks you how many caps he can get at most in the given `M` after he treats all his friends.

Remember, *Edward* is *GSF*, so he has enough money to buy *N* bottles of cola, But he can not take the caps and then give the Cola to his friends; Moreover, he can not buy the Cola for himself, too. And he can borrow
unlimited caps from someone (such as *Dai*), too. Of course, he needs to
return all the caps he has borrowed at last.

#### Input

The input contains no more than 30 test cases. Please notice that there's no empty line between each test cases.

For each test case, first line has two integers `N` (1 ≤
`N` ≤ 100000) - the number of his friends and `T` (1 ≤
`T` ≤ 10000) - the number of the queries *Edward* asks.

The following `N` lines, each line contains two integers
`Pi` and `Qi` (0 ≤ `Pi, Qi` ≤ 1000), which
shows the `i`^{th} friend will give back `Pi` caps for *Normal Cola* and `Qi` caps for *Gift Cola*.

The following `T` lines, each line contains an integer `M`
(1 ≤ `M` ≤ 1000), which means *Edward* can use
`M` caps to exchange for one *Gift Cola*.

Process to END_OF_FILE.

#### Output

For each test case, you should output `T` lines, each line has an integer - the maximal number of caps *Edward* can get after he treats all his friends.

#### Sample Input

2 1
2 0
0 2
2

#### Sample Output

2

Author:

**DAI, Longao**
Submit
Status