Задача №113450. Шпионы Его Величества
«Знание наперед нельзя получить от богов и демонов,
нельзя получить и путем умозаключений по сходству,
нельзя получить и путем всяких вычислений.
Знание положения противника можно получить
только от людей» (Сунь Цзы, «Искусство войны»)
Для поднятия престижа Короны среди граждан Королевства, Его Величеству Бубею Второму понадобилась небольшая победоносная война. В качестве цели был выбран маленький приграничный город. Королевским шпионам было дано задание узнать численность войск, находящихся в городе. Так как ежедневно пересчитывать всех солдат в целом городе очень сложно, то было решено что такой подсчет будет сделан только один раз. Затем шпионы будут только наблюдать за прибывающими или убывающими из города частями (уже не с точностью до одного человека, а с точностью до войсковой единицы: взвод, рота, полк) и ежедневно докладывать в Столицу.
Однако не все войсковые единицы противника могут состоять из одинакового числа солдат. Поэтому для каждой такой единицы в Военном Министерстве введены специальные поправки.
Пусть известно начальное количество солдат противника в городе и известно какие войсковые единицы и в каком порядке покидали город или входили в него. Напишите программу, которая по этим данным вычислит максимально возможное количество солдат в городе на текущий момент.
В первой строке файла input.txt записано начальное количество солдат (целое, положительное, не превышает 3000). Во второй строке записано число P (целое, положительное, не более 10) – количество названий разных войсковых единиц в армии потенциального противника. Следующие P строк имеют такой формат: <название войсковой единицы><численность><поправка>. Название войсковой единицы – строка, содержащая только заглавные буквы английского алфавита длины не более 10 символов. Численность – целое положительное число не более 10000, поправка – целое положительное число не более 100.
Пример такой строки:
BRIGADE 2000 50 – это означает что в войсковой единице BRIGADE может быть от 1950 до 2050 солдат (поправка действует в обе стороны).
В следующих строках файла указаны данные из донесений шпионов по одному донесению в строке. Формат донесения <знак><название войсковой единицы>, где знак ‘+’ означает что единица вошла в город, ‘-’ – что единица покинула город. Гарантируется, что количество солдат в городе в любой момент времени не превышает \(10^6\).
Количество солдат также не может быть отрицательным (гарантируется, что входные данные непротиворечивы).
В файл output.txt выведите единственное число – максимально возможную численность солдат в городе.
Комментарий к первому примеру: было 500 солдат, затем в город вошла BRIGADE численностью от 900 до 1100 (максимально 1100, поэтому прибавляем это число), затем вошла ARMY численностью от 2500 до 3500, а в конце BATTALION (от 450 до 550 человек).
Комментарий ко второму примеру: было 500 солдат, затем BATTALION (от 450 до 550) покинул город. В городе осталось от 0 до 50 солдат, берем максимальное по условию. Затем в город вошло от 450 до 550 солдат).
500 3 BATTALION 500 50 BRIGADE 1000 100 ARMY 3000 500 +BRIGADE +ARMY +BATTALION
5650
500 1 BATTALION 500 50 -BATTALION +BATTALION
600