Limits 2s, 512 MB

A grand book fair is taking place in your city, showcasing a dazzling array of books and publications. Safwan is a passionate book lover going to this book fair with a goal to buy as many books as possible.

There are nn unique books available at the fair, each with its own price and publication id. Also, there are mm publications participating in the fair, each offering a special discount on the total amount of the books you bought from them. Suppose you bought total 22 books with prices 20,3020, 30 from publication 1 and publication 1 is offering a discount amount of 6060. Then you can buy these 22 books for free. If the books price are 30,4030, 40, then you can buy these books spending 30+4060=1030+40-60=10 amount.

Safwan will be asked qq queries. In each query, he will be given an amount. To maximize his reading pleasure, he will always try to purchase the maximum number of books with the given amount. Would you like to help him?

N. B. You can’t buy the same book multiple times.


The first line of the input contains three integers 1n1061 \leq n \leq{10^6}, 1m1061 \leq m \leq{10^6}, 1q1051 \leq q \leq 10^5. Note that, mm is always less than or equal to nn and there is at least one book of every publication.

Each of the next nn lines consists of two integers price\texttt{price} (1price1012)(1 \leq \texttt{price} \leq 10^{12}) and publicationId\texttt{publicationId} (1publicationIdm)(1 \leq \texttt{publicationId} \leq m) of ii-th book.

Next line contains an array discounts\texttt{discounts} of mm integers discounts[1],discounts[2],,discounts[m]\texttt{discounts}[1], \texttt{discounts}[2], …, \texttt{discounts}[m] where 0discounts[i]10180 \leq \texttt{discounts}[i] \leq 10^{18} means ii-th publisher will offer this discount if you buy one or more books from their collection.

Each of the next qq lines contains an integer which denotes the amount (0amount1018)(0 \leq \texttt{amount} \leq 10^{18}) of that query.


For each query, print maximum number of books Safwan can buy with the given amount of that query. See the sample input output for more clarification.


5 2 3
5 1
5 1
6 1
7 2
12 2
6 0


Login to submit.


81% Solution Ratio
AST_TheCoderEarliest, 2M ago
prodip_bsmrstuFastest, 0.3s
prodip_bsmrstuLightest, 25 MB
kotoshogiku.510125Shortest, 770B
Toph uses cookies. By continuing you agree to our Cookie Policy.