Tutor Simulation

You need to compute a sequence of actions that maximizes the cash earned in a tutor simulation game. The actions are earning cash from tuition (TEACH), studying in college to raise your knowledge (TRAIN), and buying books (BUY). TRAIN raises your tuition income. BUY cuts the time units each TRAIN action consumes. Every action consumes time units, and only maxTimeUnits of them are available for work.

Like all games, the puzzle difficulty depends on the game variables and certain rules. This task has 4 game variables and 5 game rules. Value ranges are provided where appropriate.

Game variables

1. maxTimeUnits (10 - 1000): the maximum number of time units in the simulation game.
2. learningRate (1, 2, 4, or 8): scales down the time units consumed by a TRAIN action, based on the number of book in your possession.
3. paybackRate (5, 10, or 20): scales up the tuition income earned from a TEACH action, based on the knowledge level.
4. bookCost: an array of 4 integers in non decreasing order where the $i$-th integer is the cost of the $i$-th book. (The cost of each book is in the range $5 to $500.)

Game rules

1. Before the simulation starts you have maxTimeUnits left, your cash is 0, your knowledge is 0, and you have 0 book.
2. The simulation game lasts for maxTimeUnits. Your aim is to obtain as much cash as possible.
3. Every TEACH action spends 2 time units. The formula below gives the tuition income per TEACH action. That is, the more knowledge that you have, the higher your income will be.
   income = 10 + min(20, knowledge) * paybackRate
4. Every TRAIN action costs 20 dollars and it will increase the knowledge level by 1 unit. The formula below gives the trainingTime per TRAIN action. That is, the more book or the higher learningRate that you have, the lower your trainingTime will be.
   trainingTime = max(1, (int)(8 / max(1, book * learningRate)))
5. There are 4 books in this game. The $i$-th BUY action will buy the $i$-th book. It takes $i$ time units to buy the $i$-th book (0-based indexing, so the first book can be bought with 0 time unit) and the cost of the $i$-th book is stated in bookCost[i]. As there are at most 4 books, you can perform at most 4 BUY actions.

Write a program that reads in the game variable values and determines the best possible sequence of actions. You need to implement a planner so that your cash is maximum at some time unit $t$ between 0 and maxTimeUnits. However, you should not violate the following two constraints:

1. You cannot overshoot maxTimeUnits when choosing an action.
2. You cannot incur negative cash at any point, so you must be able to pay for any TRAIN or BUY action.

For example, suppose maxTimeUnits, learningRate, and paybackRate are 13, 8, and 20, respectively, and the 4 books cost $5, $50, $100, and $200.

Since you have 13 time units, a simple plan is to perform TEACH 6 times, which already earns 6 * (10 + min(20, 0) * 20) = 6 * 10 = $60. That is not the best answer. The optimal plan for these values reaches cash = $95 and runs like this:

The input, from standard input, consists of two lines. The first line contains 3 integers, which are maxTimeUnits, learningRate, and paybackRate. The second line contains 4 integers where the $i$-th integer is the cost of the $i$-th book.

Print a single integer to standard output: the maximum cash that you can gain.