Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача C. Монтаж

Задачу добавил: alef

Успешно сдано решений: 231

Ограничения по времени: 2 с на тест

Ограничения по памяти: 256 Мб

Плохая погода мешает не только ответственным за газон. Бригада, которая осуществляет монтаж кресел на трибунах, тоже полагает, что при дожде и сильном ветре качество работы будет слишком низким, и поэтому в плохую погоду занимается тем, что ожидает хорошую погоду.

В некоторые дни на стадион привозят очередную партию кресел; а в некоторые дни приезжает инспектор, который проверяет качество выполненных работ, а также фиксирует, сколько всего кресел уже смонтировано. Кресла на стадион всегда привозят рано утром, а инспектор всегда приезжает в конце рабочего дня.

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

Инженер хочет назвать минимально возможное положительное количество кресел, которые можно смонтировать в течение рабочего дня, но так, чтобы это количество не противоречило известным данным. Как понятно, бригада не может монтировать ещё не привезённые кресла, а количество смонтированных кресел в конце дня очередной инспекторской проверки должно совпасть с количеством, зафиксированным инспектором. 

Заметим, что бригада в какие-то дни может монтировать меньшее количество кресел, нежели то, которое назовет инженер. 

Ваша задача — определить, какое число следует назвать инженеру. 

Входные данные

В первой строке содержится целые числа n и m (1 ≤ n ≤ 105,  1 ≤ m ≤ 2·n) — количество дней работы бригады и количество записей о доставке кресел и приезде инспекторов.

Запись #j о доставке кресел или о приезде инспектора состоит из трёх чисел — djtjcj , где dj — номер дня, в который сделана запись, tj = 1 означает, что в этот день на стадион привозили кресла, а tj = 2 — что в этот день на стадион приезжал инспектор. Если tj = 1, то 1 ≤ cj ≤ 104.

Гарантируется, что все входные данные корректны.

Гарантируется, что для каждого дня существует не более одной записи о доставке кресел и не более одной записи о визите инспектора. 

Гарантируется, что записи следуют в хронологическом порядке, т.е. d1 ≤ d2 ≤ ... ≤ dm. Если для одного и того же дня есть и запись о доставке кресел, и запись о приезде инспектора, они присутствуют именно в таком порядке.

Также гарантируется, что все значения cj при tj = 2 образуют корректную неубывающую последовательность, а для каждого cj при tj = 2 верно, что .

Во второй строке входного файла содержатся величины d1, d2, ..., dm, в третьей строке — величины t1, t2, ..., tm, в четвёртой строке — величины c1, c2, ..., cm.

Выходные данные

Выведите положительное целое число p — количество кресел, которое следует назвать инженеру.

Система оценки

Подзадача 1 (до 20 баллов)

1 ≤ n ≤ 100.

Баллы начисляются за каждый пройденный тест.

По запросу сообщается результат проверки на каждом тесте.

Подзадача 2 (до 80 баллов)

Все величины из условия могут принимать любые допустимые значения.

Баллы начисляются в случае прохождения всех тестов группы.

По запросу сообщается номер первого непройденного теста.

Пример

входные данные
10 7
2 4 5 5 7 8 8
1 2 1 2 1 1 2
11 8 1 9 3 7 14
выходные данные
3

Примечание

Поясним приведённый пример.

Как можно видеть, кресла привозили во 2, 5, 7 и 8 день. Инспектора посещали стадион в 4, 5 и 8 день.

Можно удостовериться, что если в течение дня бригада могла смонтировать не более 3 кресел, то и данные о привозе кресел, и данные о приезде инспекторов являются корректными. Например, монтаж кресел мог выполняться следующим образом:

день:                  1   2   3   4   5   6   7   8   9   10

смонтировано:    0   3   2   3   1   0   3   2    3   2

Действительно, в первый день бригада не монтировала кресел, и это вполне понятно, поскольку кресел на стадион ещё не привозили.

Во второй день было доставлено 11 кресел; бригада смонтировала 3 кресла (условие не больше 3 соблюдено); в третий — 2 кресла, в четвёртый — снова 3 кресла. Суммарно это 8 кресел, что не превосходит количества кресел, которые в принципе могли быть смонтированы к этому дню, а также совпадает с данными инспектора, приезжавшего в четвёртый день. 

Далее, в пятый день привезли одно кресло, и не смонтированных кресел стало 4 (3 осталось от предыдущей партии). Бригада в этот день смонтировала только одно кресло. Вечером инспектор насчитал 9 смонтированных кресел, а в распоряжении бригады осталось 3 пригодных для монтажа кресла.

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

Впрочем, утром восьмого дня привезли ещё 7 кресел (и суммарно их стало 10), а в течение восьмого дня бригада смонтировала 2 кресла. Суммарно к концу восьмого дня получается 14 кресел, что совпадает с подсчётами инспектора, посетившего стадион вечером этого дня. 

Несмонтированными остались 8 кресел. В девятый день бригада могла бы смонтировать 3 кресла, в десятый день — два кресла (могли быть и другие значения, ибо до посещения самого главного инспектора никто об этом не узнает). 

Также несложно убедиться, что 2 не может быть ответом. Если считать, что в день можно смонтировать не более 2 кресел, то получить 8 смонтированных кресел в четвёртый день (первое посещение инспектора) бригада никак не могла. Впервые кресла завезли только во второй день, и даже если бы каждый день бригада монтировала по 2 кресла, то к концу четвёртого дня смонтированных кресел было бы только 6.

Сдать задачу

Задать вопрос жюри по этой задаче