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 $n$ unique books available at the fair, each with its own price and publication id. Also, there are $m$ 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 $2$ books with prices $20, 30$ from publication 1 and publication 1 is offering a discount amount of $60$. Then you can buy these $2$ books for free. If the books price are $30, 40$, then you can buy these books spending $30+40-60=10$ amount.

Safwan will be asked $q$ 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 $1 \leq n \leq{10^6}$, $1 \leq m \leq{10^6}$, $1 \leq q \leq 10^5$. Note that, $m$ is always less than or equal to $n$ and there is at least one book of every publication.

Each of the next $n$ lines consists of two integers $\texttt{price}$ $(1 \leq \texttt{price} \leq 10^{12})$ and $\texttt{publicationId}$ $(1 \leq \texttt{publicationId} \leq m)$ of $i$-th book.

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

Each of the next $q$ lines contains an integer which denotes the amount $(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.

Input | Output |
---|---|

5 2 3 5 1 5 1 6 1 7 2 12 2 6 0 23 35 50 | 4 5 5 |

Login to submit.

81%
Solution Ratio

AST_TheCoderEarliest,

prodip_bsmrstuFastest, 0.3s

prodip_bsmrstuLightest, 25 MB

kotoshogiku.510125Shortest, 770B

Toph uses cookies. By continuing you agree to our Cookie Policy.