P9789 [ROIR 2020] ATM (Day 2)

**Translated from [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day 2 T3.** ***[Банкомат](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***, translated by ksyx. You are developing an ATM with multiple denominations, called the Universal ATM. Specifically, there are $n$ kinds of banknotes with denominations $a_1,~a_2,~\ldots,~a_n$ sorted in increasing order, i.e. for $i>2$, $a_{i-1}

The first line contains an integer $n$, the number of denominations. The next line contains $n$ integers $a_i$. The third line contains an integer $q$, the number of queries. The next $q$ lines each contain an integer $b_i$.

For each query, output two integers: the total amount withdrawn by the customer in the case where the number of banknotes is maximized, and the number of banknotes. If multiple withdrawal requests not exceeding the maximum total amount in the input correspond to this number of banknotes, output any one of them.

#### Sample 1 Explanation One feasible solution for each query is as follows: $2=1+1$, $8=5+1+1+1$, $49=10+10+10+10+5+1+1+1+1$. #### Constraints For $100\%$ of the testdata, $1\le n\le 2\times 10^5$, $1=a_1