Deposits
Турнир за Купата на Декана, 2019
Time Limit: 0.4s, Memory Limit: 64MiB
В държавата, където живее Ели, банковите влогове на хората са подсигурени до M евро. Например, ако M = 100,000 и дадена банка, в която Ели има влог от 42,666 евро, фалира, то държавата ще ѝ върне всичките 42,666 евро. Ако, обаче, Ели е имала 421,337 евро, то държавата ще ѝ върне само парите, които са подсигурени (100,000), а останалите 321,337 ще бъдат безвъзвратно загубени.

Поради проведените наскоро стрес-тестове на банките, управниците на държавата решиха, че ще е хубаво в най-скоро време да променят максималния подсигурен размер M. Те знаят броя на всички вложители N и размерите на техните влогове A1, A2, ..., AN. За да определят новото M на тях им трябва програма, който бързо да може да пресмята колко пари ще трябва да върнат на вложителите, ако M е някакво конкретно число и банката фалира. На вас се пада честта да напишете тази програма.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N - броят вложители в страната. На следващия ред ще има N цели числа A1, A2, ..., AN - размерът на влоговете. На третия ред ще бъде зададено едно цяло число Q - броя въпроси, на които вашата програма трябва да отговори. На четвъртия ред ще бъдат зададени Q цели числа М1, М2, ..., МQ - различни суми, до които могат да са подсигурени влоговете.
Изход
На стандартния изход изведете Q на брой реда с по едно цяло число - сумата, която държавата трябва да изплати на N-те вложители за всяко от дадените Mi.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ Ai ≤ 1,000,000,000
  • 1 ≤ Q ≤ 100,000
  • 1 ≤ Mi ≤ 1,000,000,000
Примерен Вход Примерен Изход
8 42 13 17 25 30 25 19 37 3 20 17 33 149 132 195
В първия случай M = 20. Влоговете с размери 13, 17, и 19 ще бъдат възстановени изцяло (за 13 + 17 + 19 = 49 евро, платени от държавата). Останалите 5 влога ще бъдат възстановени само до лимита от 20, което прави 5 * 20 = 100 евро. Сумарно, държавата ще трябва да плати 49 + 100 = 149 евро.
Мрън!