The problem is basically monopoly but you don't need to roll dices or stuffs, we have $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ positions each of which are all empty. We can play any number of rounds by each rounds we choose an index $$$i$$$, if it's empty, we'll build a house on that position which will cost us $$$A_i$$$, and gives us 1 points, but if it's a house already, we'll transform the house to a apartment, which will cost us $$$B_i$$$, and gives us 1 points, if it's already an apartment we'll do nothing, which gives us nothing and cost us nothing (so there's no reason to do this). We always want to maximize the amount of points. (We can make an apartment on the position $$$i$$$ if and only if the position $$$i$$$ is a already a house)

There will be $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ queries, on the $$$ith$$$ query $$$(1 \leq i \leq Q)$$$ we have a budget of $$$X_i$$$, which means that the total sums of cost cannot exceed $$$X_i$$$. We want to know that, for each queries $$$i$$$ $$$(1 \leq i \leq Q)$$$ what is the maximum amount of points we can possibly get?

Again on constraints:

• $$$1 \leq N,Q \leq 10^5$$$

• $$$1 \leq A_i,B_i \leq 10^{14}$$$

• $$$1 \leq X_i \leq 2 \cdot 10^{14}$$$