Автоботы отважились на штурм базы десептиконов. Из-за эффекта внезапности множество десептиконов полегло на месте, а остальные начали судорожно прятаться в бункеры, которые начали закрываться. Оптимус Прайм хочет добить как можно больше десептиконов. Для этого он решил использовать новую разработку автоботов — бомбу «Антибункер».

Принцип работы бомбы заключается в том, что ее можно кинуть внутрь бункера, а когда тот закроется — взорвать, и тогда она убьет всех, кто был внутри. Единственное ее неудобство заключается в том, что взрывается она неавтоматически. То есть Оптимусу, после того, как он кинет бомбу, придется ждать закрытия бункера, чтобы взорвать всех внутри, и лишь потом он сможет поехать дальше.

Оптимус собирается проехать мимо каждого бункера ровно один раз, посетив их в порядке возрастания номеров. К счастью, он знает, на какой минуте закроется каждый из бункеров, а также количество десептиконов в каждом из бункеров. Между бункерами Оптимус перемещается очень быстро — перемещение между любой парой бункеров занимает у него ровно одну минуту. Если он проехал бункер, он уже не сможет вернуться обратно.

Оптимус Прайм просит вас помочь ему рассчитать, какое наибольшее количество врагов он сможет убить, и в какие бункеры нужно бросить бомбу для этого.

Черный ящик организован наподобие примитивной базы данных. Он может хранить набор целых чисел и имеет выделенную переменную i . В начальный момент времени черный ящик пуст, а значение переменной i =0. Черный ящик обрабатывает последовательность поступающих команд (запросов). Существуют два типа запросов:

• ADD: положить в черный ящик элемент;
• GET: увеличить значение i на 1 и выдать i - ый минимальный из содержащихся в черном ящике элементов. Напомним, что i - ым минимальным называется число, стоящее на i - ом месте после сортировки элементов черного ящика в порядке неубывания.

Рассмотрим возможную последовательность из 11 запросов:

№	Запрос	i	Содержимое черного ящика после запроса (элементы расположены в порядке неубывания)	Ответ
1	ADD (3)	0	3
2	GET	1	3	3
3	ADD (1)	1	1, 3
4	GET	2	1, 3	3
5	ADD (-4)	2	-4, 1, 3
6	ADD (2)	2	-4, 1, 2, 3
7	ADD (8)	2	-4, 1, 2, 3, 8
8	ADD (-1000)	2	-1000, -4, 1, 2, 3, 8
9	GET	3	-1000, -4, 1, 2, 3, 8	1
10	GET	4	-1000, -4, 1, 2, 3, 8	2
11	ADD (2)	4	-1000, -4, 1, 2, 2, 3, 8

Требуется разработать эффективный алгоритм, обрабатывающий заданную последовательность запросов. Максимальное допустимое количество запросов ADD и GET — по 30000 каждого типа. Последовательность запросов будем задавать двумя наборами чисел:

1. Последовательностью включаемых в черный ящик элементов A (1), A (2), ... A ( M ) . Значения A — целые числа, не превосходящие по абсолютной величине 2 000 000 000, 1 ≤ M ≤ 30000 . Для примера 1 имеем A =(3, 1, -4, 2, 8, -1000, 2).
2. Последовательностью u (1), u (2), ... u ( N ) , задающей количество содержащихся в черном ящике элементов в момент выполнения первой, второй, ..., N - ой команды GET. Для примера 1 имеем u =(1, 2, 6, 6).

Схема работы черного ящика предполагает, что последовательность натуральных чисел u (1), u (2), ... u ( N ) упорядочена по неубыванию, N ≤ M и для всех p (1 ≤ p ≤ N ) выполняется соотношение p ≤ u ( p ) ≤ M . Последнее следует из того, что для p - го элемента последовательности u мы выполняем запрос GET, выдающий p - ое минимальное число из набора A (1), A (2), ..., A ( u ( p )) .

Как известно, Нью-Йорк большой город. На главной улице находится N небоскребов в ряд, в i - м небоскребе есть A _i свободных офисов. Недавно в городе образовались M компаний. Каждой из них конечно нужны офисы, но управляющие i - й компании хотят получить по офису в каждом небоскребе с L _i по R _i . Напишите программу, которая вычислит, какое максимальное количество компаний может получить офисы на главной улице Нью-Йорка в соответствии с их требованиями.

Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций АСМ (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NЕЕRС (North-Eastern European Regional Contest). Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного вуза не может проходить более чем k команд. При этот из всех таких множеств выбирается то, в котором сумма мест занятых этими командами в полуфинальных соревнованиях минимальная возможная. Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и k определить, какие команды будут приглашены к участию в финале чемпионата мира.