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 ≤ 10000
• 1 ≤ Q ≤ 100000
• 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

#include <bits/stdc++.h>

using namespace std;

ifstream cin("cb3.in");
ofstream cout("cb3.out");

int a[10001] , n;
long long int sp[10001];

int cb(int x)
{
    int st = 1 , dr = n;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(sp[mij] > x)
            dr = mij - 1;
        if(sp[mij] < x)
            st = mij + 1;
        if(sp[mij] == x)
            return mij;
    }
    return dr;
}

int main()
{
    int q;
    cin >> n >> q;
    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i];
    sort(a+1 , a+n+1);
    for(int i = 1 ; i <= n ; ++i)
        sp[i]=sp[i-1]+a[i];
    int x;
    for(int i = 1 ; i <= q ; ++i)
    {
        cin >> x;
        cout << cb(x) << '\n';
    }
    return 0;
}