CosmoCraft

2인용 전략 게임 CosmoCraft에서는 경제를 키워 상대를 물리칠 만큼 강한 군대를 양성해야 합니다. 여러분은 일꾼, 생산 시설, 군대를 관리하며, 게임의 핵심은 가진 돈을 이 셋에 어떻게 배분하느냐입니다. 게임은 턴 단위로 진행됩니다.

• 일꾼은 매 턴 1달러의 수입을 줍니다.
• 생산 시설은 한 턴에 한 번, 1달러를 들여 군대 1기 또는 일꾼 1명 중 하나를 생산할 수 있습니다(시설 하나가 한 턴에 만들 수 있는 것은 최대 1개).
• 새 생산 시설을 짓는 데에는 1달러가 듭니다.
• 군대는 상대와 싸우는 수단입니다.

여러분은 일꾼 $n$명과 생산 시설 $k$개로 시작합니다. 매 턴 먼저 현재 활동 중인 일꾼 수만큼 수입을 얻고(이전 턴에서 남겨 둔 돈에 합산됩니다), 그 돈으로 새 일꾼, 새 군대, 새 생산 시설을 원하는 대로 조합해 구매할 수 있습니다. 이번 턴에 만든 일꾼과 시설은 다음 턴부터 활동하지만, 군대는 즉시 사용할 수 있습니다. 쓰지 않은 돈은 다음 턴으로 이월됩니다.

상대는 처음 $t-1$개의 각 턴이 끝날 때 여러분을 공격합니다. 턴 $i$의 세기 $a_i$인 공격을 버티려면 그 순간 보유한 군대 수가 $a_i$ 이상이어야 하며, 버틴 뒤에는 군대에서 $a_i$기가 사라집니다(남은 만큼만 유지). 보유한 군대가 $a_i$보다 적으면 패배합니다. 게임은 $t$턴 동안 진행되며, 마지막 턴에는 들어오는 공격이 없습니다.

여러분은 이 상대와 여러 번 겨뤄 봐서 매 공격의 세기를 정확히 알고 있습니다. 그래서 철저히 수비적으로 플레이하기로 합니다. 즉, 모든 공격을 버티면서 마지막 반격을 위해 가능한 한 큰 군대를 비축합니다. 상대의 모든 공격을 버텨야 한다는 조건 아래, 게임이 끝났을 때 가질 수 있는 가장 큰 군대의 규모는 얼마입니까?

입력에는 여러 개의 테스트 케이스가 있습니다. 각 테스트 케이스는 세 정수로 이루어진 줄로 시작합니다:

n k t

여기서 $n$ ($1 \le n \le 100$)은 시작 일꾼 수, $k$ ($1 \le k \le 100$)는 시작 생산 시설 수, $t$ ($1 \le t \le 10000$)는 턴 수입니다. 다음 줄에는 공백 하나로 구분된 $t-1$개의 정수 $a_i$ ($0 \le a_i \le 2^{63}-1$)가 주어지며, $a_i$는 턴 $i$가 끝날 때 상대가 가하는 공격의 세기(사용하는 군대 수)입니다. 입력은 세 개의 0으로 이루어진 줄로 끝납니다.

각 테스트 케이스에 대해 게임이 끝났을 때 가질 수 있는 가장 큰 군대의 규모를 정수 하나로 출력하세요. 모든 공격을 버티는 것이 불가능하면 $-1$을 출력합니다. 각 답은 한 줄에 하나씩, 여분의 공백이나 답 사이의 빈 줄 없이 출력하세요. 모든 유효한 입력의 답은 부호 있는 64비트 정수 범위에 들어가도록 보장됩니다.