Rezolvare PBinfo #2789

Se consideră un șir de numere naturale nenule a[1], a[2], ..., a[n]. Asupra șirului se efectuează Q interogări de forma: care este numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S ?

Cerință

Trebuie să răspundeți la cele Q interogări.

Date de intrare

Fișierul de intrare cb3.in conține pe prima linie numerele n și Q. Pe a doua linie n numere naturale nenule, separate prin spații, ce reprezintă elementele șirului. Pe următoarele Q linii se află sumele aferente celor Q interogări.

Date de ieșire

Fișierul de ieșire cb3.out va conține pe câte o linie răspunsurile la cele Q interogări.

Restricții și precizări

• 1 ≤ n ≤ 10.000
• 1 ≤ Q ≤ 100.000
• 1 ≤ S ≤ 2.000.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu:

cb3.in

5 3
1 2 3 4 5
6
17
5

cb3.out

3
5
2