CosmoCraft#3971

CosmoCraft

1 секунда

32 мегабайти

Легка

У двогравцевій грі CosmoCraft ви керуєте економікою з метою створити армію, здатну перемогти супротивника. Ви керуєте будівництвом робітників, виробничих потужностей та армійських підрозділів; завдання — балансувати ресурси між цими компонентами. Гра відбувається по ходах.

Кожен робітник приносить дохід із швидкістю $1$ долар за хід.
Кожна виробнича потужність дозволяє виробляти або робітника, або армійський підрозділ за $1$ долар кожен. (За хід на одній потужності можна виробити лише $1$ підрозділ або $1$ робітника.)
Створення виробничої потужності коштує $1$ долар.
Армійські підрозділи необхідні для бою з супротивником.

Ви починаєте з $n$ робітниками і $k$ виробничими потужностями. У кожному ході ви можете витрачати дохід, отриманий від робітників, на будь-яке поєднання робітників, підрозділів армії та виробничих потужностей. Робітники, вироблені в поточному ході, не приносять дохід до наступного ходу; так само, виробничі потужності, побудовані в поточному ході, не активні до наступного ходу. Будь-який невикористаний дохід переноситься на наступний хід.

Наприкінці кожного ходу ви можете використати всі підрозділи армії, які маєте, для атаки супротивника. Якщо у вас строго більше армійських підрозділів, ніж у супротивника, супротивник негайно програє, а ви зберігаєте різницю у кількості підрозділів. В іншому випадку ваша армія знищується, а супротивник зберігає різницю у підрозділах. (Супротивник може потім контратакувати, але ви не програєте одразу.) Гра закінчується після $t$ ходів, після чого обидва гравці зазвичай атакують усіма своїми підрозділами армії, і перемагає той, у кого армія більша.

Ви граєте проти друга і, граючи багато разів, знаєте точно, як він витрачатиме гроші в кожному ході й коли буде атака. Знаючи це, ви вирішили, що найкраща стратегія — оборона: ви просто бажаєте вижити після кожної атаки й накопичити якнайбільшу армію для останньої атаки, щоб (сподіваємося) перемогти.

Яку найбільшу кількість армійських підрозділів ви можете мати наприкінці гри, якщо мусите вижити після всіх атак друга?

Вхідні дані

У вхідних даних кілька тестових випадків. Кожен тестовий випадок починається рядком із трьома числами:

n k t

де $n$ ( $1 \leq n \leq 100$ 1 \le n \le 100) — кількість робітників на початку, $k$ ( $1 \leq k \leq 100$ 1 \le k \le 100) — кількість виробничих потужностей на початку, $t$ ( $1 \leq t \leq 10000$ 1 \le t \le 10000) — кількість ходів. Наступний рядок містить $t - 1$ t-1 цілих чисел, $a_{i}$ a_i ( $0 \leq a_{i} \leq$ 0 \le a_i \le максимальне знакове $64$ -бітне ціле число), розділених пробілами. $i$ -те число вказує силу атаки (кількість армійських підрозділів, використаних супротивником) на ході $i$ . Вхід закінчується рядком із трьох нулів.

Вихідні дані

Для кожного тесту виведіть одне ціле число — максимальну кількість армійських підрозділів, які ви можете мати наприкінці гри. Виведіть $- 1$ , якщо вижити неможливо. Кожне число виводьте з нового рядка, без пробілів чи порожніх рядків між відповідями. Хоча деякі вхідні дані можуть давати дуже великі відповіді, всі суддівські дані мають відповіді, що помістяться в знакове $64$ -бітне ціле число.

Приклади

Приклад 1