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-bit integer), розділених одним пробілом. i-те число вказує на силу атаки (тобто кількість армійських підрозділів, які ваш супротивник використовує в цій атаці) на ході i. Вхідні дані закінчуються рядком з трьома 0.
Вихідні дані
Для кожного тестового випадку виведіть одне ціле число, яке вказує на максимальну кількість армій, яку ви могли б мати наприкінці гри. Виведіть -1, якщо вижити неможливо. Виведіть кожне число в окремому рядку, без пробілів, і не друкуйте порожніх рядків між відповідями. Хоча можливо, що деякі вхідні дані можуть генерувати надмірно великі відповіді, всі вхідні дані судді дають відповіді, які помістяться в знакове 64-бітове ціле число.