Задача C. Монтаж
Задачу добавил: alef
Успешно сдано решений: 245
Ограничения по времени: 2 с на тест
Ограничения по памяти: 256 Мб
Плохая погода мешает не только ответственным за газон. Бригада, которая осуществляет монтаж кресел на трибунах, тоже полагает, что при дожде и сильном ветре качество работы будет слишком низким, и поэтому в плохую погоду занимается тем, что ожидает хорошую погоду.
В некоторые дни на стадион привозят очередную партию кресел; а в некоторые дни приезжает инспектор, который проверяет качество выполненных работ, а также фиксирует, сколько всего кресел уже смонтировано. Кресла на стадион всегда привозят рано утром, а инспектор всегда приезжает в конце рабочего дня.
С начала монтажа кресел прошло n дней, а завтра рано утром проверять стадион приедет самый главный инспектор. По сведениям из надёжных источников, он полагает, что бригада много времени простаивает, и крайне недоволен этим. Он уже заинтересовался, какое максимальное количество кресел можно смонтировать в течение рабочего дня. Инженер, которого самый главный инспектор попросил дать ответ на этот вопрос, является хорошим товарищем бригадира и хочет ему помочь.
Инженер хочет назвать минимально возможное положительное количество кресел, которые можно смонтировать в течение рабочего дня, но так, чтобы это количество не противоречило известным данным. Как понятно, бригада не может монтировать ещё не привезённые кресла, а количество смонтированных кресел в конце дня очередной инспекторской проверки должно совпасть с количеством, зафиксированным инспектором.
Заметим, что бригада в какие-то дни может монтировать меньшее количество кресел, нежели то, которое назовет инженер.
Ваша задача — определить, какое число следует назвать инженеру.
В первой строке содержится целые числа n и m (1 ≤ n ≤ 105, 1 ≤ m ≤ 2·n) — количество дней работы бригады и количество записей о доставке кресел и приезде инспекторов.
Запись #j о доставке кресел или о приезде инспектора состоит из трёх чисел — dj, tj, cj 
, где 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.