CosmoCraft
В игре для двух игроков CosmoCraft вы управляете экономикой, чтобы создать армию, способную победить противника. Ваша задача — строить рабочих, производственные объекты и армейские единицы, балансируя ресурсы между этими элементами. Игра проходит по ходам.
Рабочие приносят доход в размере 1 доллар за ход.
Производственные объекты позволяют производить либо армейскую единицу, либо рабочего за 1 доллар. (на одном объекте можно произвести только 1 единицу или рабочего за ход)
Стоимость создания производственного объекта составляет 1 доллар.
Армия позволяет вам сражаться с противником.
Вы начинаете с n рабочих и k производственных объектов. В каждом ходу вы можете потратить доход от рабочих на создание новых рабочих, армейских единиц и производственных объектов. Рабочие, произведенные в текущем раунде, начнут приносить доход только в следующем; аналогично, производственные объекты станут активными только в следующем раунде. Любой неиспользованный доход переносится на следующий раунд.
В конце раунда вы можете атаковать противника всей своей армией; если у вас больше единиц, чем у противника, он проигрывает, и вы сохраняете разницу в численности армии. В противном случае ваша армия уничтожается, и у противника остается разница в численности. (возможно, он контратакует, но вы не проигрываете сразу). Игра заканчивается после t ходов, и побеждает тот, у кого больше армия.
Вы играете против друга и знаете, как он распределит свои ресурсы и когда атакует. Зная это, вы решили играть в обороне — ваша цель пережить все атаки и накопить максимальную армию для контратаки в конце игры.
Какую максимальную армию вы можете иметь в конце игры, если должны пережить все атаки друга?
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается с строки с тремя целыми числами:
n k t
где n (1 ≤ n ≤ 100) — начальное количество рабочих, k (1 ≤ k ≤ 100) — начальное количество производственных объектов, и t (1 ≤ t ≤ 10000) — количество ходов. Следующая строка содержит t-1 целых чисел, a_i (0 ≤ a_i ≤ Maxsigned 64-битное целое число), разделенных пробелами. i-е число указывает на силу атаки (число армейских единиц противника) на ходу i. Входные данные заканчиваются строкой с тремя 0.
Выходные данные
Для каждого теста выведите одно целое число, указывающее максимальное количество армий, которое вы могли бы иметь в конце игры. Выведите -1, если невозможно выжить. Выведите каждое число на отдельной строке, без пробелов, и не оставляйте пустых строк между ответами. Хотя некоторые входные данные могут давать очень большие ответы, все они помещаются в знаковое 64-битное целое число.