Задача №112526. Нью-Йорк
Как известно, Нью-Йорк большой город. На главной улице находится N небоскребов в ряд, в i - м небоскребе есть A i свободных офисов. Недавно в городе образовались M компаний. Каждой из них конечно нужны офисы, но управляющие i - й компании хотят получить по офису в каждом небоскребе с L i по R i . Напишите программу, которая вычислит, какое максимальное количество компаний может получить офисы на главной улице Нью-Йорка в соответствии с их требованиями.
В первой строке входных данных записаны 2 числа N и M (1 ≤ N , M ≤ 100000) . В следующих N строках записано по одному числу A i (1 ≤ A i ≤ 100000) . В следующих М строках записаны пары чисел L i и R i (1 ≤ L i ≤ R i ≤ N ) .
Выведите одно число — максимальное количество компаний, которые могут получить офисы на главной улице Нью-Йорка.
5 4 1 3 2 1 3 1 3 2 5 2 3 4 5
3