Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Након што се пензионисао у Врчинсофту и постао велемајстор програмирања на Врчинској Сили, Марко је одлучио да нађе нови хоби. Пошто сви знају да је Врчин кишно место, одлучио је да скупља кишу у својих \(N\) бурића.
Он их је поређао у ред с лева на десно и нумерисао их бројевима од \(1\) до \(N\), тако да је буре са бројем \(1\) најлевље. Буре \(i\) има капацитет од \(a_i\) литара.
Марко зна да ће наредних \(M\) дана да пада киша, али на јако специфичан начин – \(i\)-тог дана киша ће падати тако да вода упада искључиво у буриће нумерисане бројевима од \(l_i\) до \(r_i\) (укључујући и њих). Ако киша доспева у неко буре, у дану у њега упадне тачно један литар кише. Ако се Марку не свиди временска прогноза за тај дан, он има могућност да прекрије све буриће, како киша тог дана не би упала у њих.
Марко воли да сакупи што више воде, али још више мрзи кад му се прелије неко буре. Пошто је окачио тастатуру о клин, замолио је вас да израчунате – колико најмање дана је потребно да прекрије све буриће, тако да се ниједно буре не прелије (не падне у њега више литара воде него што му је капацитет)?
У првом реду стандардног улаза налазе се позитивни цели бројеви \(N\) и \(M\), где је \(N\) број бурића које Марко поседује, а \(M\) број кишних дана.
У наредном реду, налази се \(N\) ненегативних целих бројева, од којих је \(i\)-ти број баш \(a_i\), капацитет \(i\)-тог бурета.
Наредних \(M\) редова садрже по два позитивна цела броја \(l_i\) и \(r_i\) који описују кишне дане.
У једином реду стандардног излаза исписати један број - најмањи број дана у којим Марко мора прекрити буриће.
5 4
3 1 0 0 3
1 3
1 2
1 5
4 53Потребно је прекрити буриће сваки дан сем другог, јер ће иначе киша упасти у буриће капацитета \(0\).
6 9
4 1 2 3 1 2
2 4
1 3
4 4
1 4
5 6
3 4
6 6
3 3
1 64