Valera has only one electrical socket in his flat. He also has m devices which require electricity to work. He‘s got n plug multipliers to plug the devices, the i-th plug multiplier has a_i sockets.

A device or plug multiplier is supplied with electricity if it is either plugged into the electrical socket, or if it is plugged into some plug multiplier which is supplied with electricity.

For each device j, Valera knows the safety value b_j which is the maximum number of plug multipliers on the path between the device and the electrical socket in his flat. For example, if b_j = 0, the device should be directly plugged into the socket in his flat.

What is the maximum number of devices Valera could supply with electricity simultaneously? Note that all devices and plug multipliers take one socket to plug, and that he can use each socket to plug either one device or one plug multiplier.

#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 2e5+20;int a[maxn],b[maxn];int num[maxn];int dp[maxn];LL sum[maxn];int n,m;bool cmp(int a,int b){    return a>b;}bool check (int val){    int begin=1,end=val;    LL res = a[1]; //能够插多少个    LL can = a[1];    int need = 1; //有没一定要插一的    int cur = 1;    while (1) {        //res += a[cur];        while (end >= begin && b[end] == need) { //一定要插这个位置            res--; can--; end--;            if (res < 0) return false;        }        if (end == begin-1) return true;        if (can == 0) return false;//        printf ("%d\n",n);        while (can && cur + 1 <= n) { //插尽量多的排插            --can; --res; ++cur;            res += a[cur];            //printf ("%d****\n",a[cur]);        }        if (cur == n) { //所有排插都用完了.            return res >= end-begin+1;        }        can = res;        need++;       // printf ("%d\n",res);    }}void work (){    scanf("%d%d",&n,&m);    for (int i=1; i<=n; ++i) scanf("%d",&a[i]);    int lenb=0;    for (int j=1; j<=m; ++j) {        int x; scanf("%d",&x);        if (x != 0) b[++lenb] = x; //0是没用的    }    sort (a+1,a+1+n,cmp);    sort(b+1,b+1+lenb,cmp);    int begin=1,end=lenb;    while (begin<=end)    {        int mid = (begin+end)/2;        if (check(mid))            begin=mid+1;        else end=mid-1;    }    printf ("%d\n",max(1,end));    return ;}int main(){#ifdef local    freopen("data.txt","r",stdin);#endif    work();    return 0;}