과외 시뮬레이션

과외 시뮬레이션 게임에서 버는 cash를 최대로 만드는 행동 순서를 계산해야 한다. 할 수 있는 행동은 과외비를 받아 cash를 버는 TEACH, 대학에서 공부해 knowledge를 올리는 TRAIN, 책을 사는 BUY 세 가지다. TRAIN은 과외 수입을 늘려 주고, BUY는 TRAIN 한 번에 드는 시간을 줄여 준다. 세 행동 모두 시간을 소모하며, 쓸 수 있는 시간은 maxTimeUnits뿐이다.

다른 게임과 마찬가지로 이 퍼즐의 난이도도 게임 변수와 규칙에 따라 달라진다. 이 문제에는 게임 변수 4개와 게임 규칙 5개가 있다. 값의 범위는 필요한 곳에 적어 두었다.

게임 변수

1. maxTimeUnits (10 - 1000): 시뮬레이션 게임에서 쓸 수 있는 시간 단위의 최댓값.
2. learningRate (1, 2, 4, 8 중 하나): 손에 있는 book 수와 함께 TRAIN 한 번이 소모하는 시간을 줄인다.
3. paybackRate (5, 10, 20 중 하나): knowledge가 높을수록 TEACH 한 번이 주는 과외 수입 income을 키운다.
4. bookCost: 비내림차순으로 주어진 정수 4개짜리 배열이며, $i$번째 정수는 $i$번째 책의 가격이다. (책 한 권의 가격은 $5 이상 $500 이하다.)

게임 규칙

1. 시뮬레이션이 시작하기 전에 남은 시간은 maxTimeUnits이고, cash는 0, knowledge는 0, book은 0권이다.
2. 시뮬레이션은 maxTimeUnits 동안 이어진다. 목표는 cash를 최대한 많이 모으는 것이다.
3. TEACH는 한 번에 시간 2를 쓴다. 한 번의 TEACH로 얻는 과외 수입 income은 아래 식과 같다. 즉 knowledge가 높을수록 수입이 커진다.
   income = 10 + min(20, knowledge) * paybackRate
4. TRAIN은 한 번에 20달러가 들고 knowledge를 1 올린다. 한 번의 TRAIN에 드는 시간 trainingTime은 아래 식과 같다. 즉 book이 많거나 learningRate가 높을수록 trainingTime이 짧아진다.
   trainingTime = max(1, (int)(8 / max(1, book * learningRate)))
5. 이 게임에 책은 4권 있다. $i$번째 BUY는 $i$번째 책을 산다. $i$번째 책을 사는 데는 시간 $i$가 들고 (인덱스는 0부터 시작하므로 첫 번째 책은 시간 0에 살 수 있다), 가격은 bookCost[i]다. 책이 많아야 4권이므로 BUY는 최대 4번 할 수 있다.

게임 변수 값을 읽어 가장 좋은 행동 순서를 정하는 프로그램을 작성하라. 0 이상 maxTimeUnits 이하인 어떤 시점 $t$에서 cash가 최대가 되도록 계획을 세우면 된다. 단, 다음 두 제약을 어기면 안 된다.

1. 행동을 고를 때 maxTimeUnits를 넘길 수 없다.
2. 어느 시점에도 cash가 음수가 되면 안 된다. 즉 TRAIN이나 BUY의 비용을 낼 수 있어야 한다.

예를 들어 maxTimeUnits, learningRate, paybackRate가 각각 13, 8, 20이고 책 4권의 가격이 $5, $50, $100, $200이라고 하자.

시간이 13이므로 TEACH를 6번 하는 단순한 방법을 쓸 수 있고, 그것만으로 6 * (10 + min(20, 0) * 20) = 6 * 10 = $60을 번다. 그러나 이 값은 최적이 아니다. 이 값들에 대한 최적해는 cash = $95이고, 과정은 아래와 같다.

표준 입력으로 주어지는 입력은 두 줄이다. 첫째 줄에는 정수 3개 maxTimeUnits, learningRate, paybackRate가 주어진다. 둘째 줄에는 정수 4개가 주어지며, $i$번째 정수는 $i$번째 책의 가격이다.

얻을 수 있는 cash의 최댓값을 정수 하나로 표준 출력에 출력한다.