Hello, Codeforces!

I am spinning with this problem for half day of thoughts and bugs. I would like to share it here with you so that we can discuss together to find some interesting things (more than a solution!).

Let's begin.

You are the player having T dollars, and you will trade on n types of commodities. The game takes place in R turns. Each turn, the price of each type is announced, and you are allowed to buy or sell goods:

• If you want to buy s[i] products of type-i, you have to pay money. Your bank account will be decreased by s[i] * (P[i] + d), where P[i] is the price of type-i, d is the extra fee in buying. s[i] products that you just bought would be transported to the storage. You cannot have more than C[i] products of type-i in your storage.

• If you want to sell s[i] products of type-i, of courses you must have at least s[i] products of type-i in the storage, which will be decreased by s[i]. After that, your bank account is gained by s[i] * (P[i] — e), where e is the extra fee in selling.

What is the biggest money in your bank account after all?

Notice: In each turn, the order of buying/selling any types is not important. But make sure that at the end of that turn, your money cannot be negative.

Input:

• The first line contains 5 non-negative integers n, T, R, d, e.
• The second line contains n non-negative integers C[1], C[2], ..., C[n]
• The next R lines, every line consists of n non-negative integers, which are P[1], P[2], ..., P[n] in the turn.

Example:

3 2 2 1 0

1 1 1

1 1 1

2 3 4

Output:

4

Constraint:

T <= 10^9

d,e <= 10^6

C[i] <= 20

n <= 5

R <= 500

Note: When R > 5, d = e = 0.

This is my code

(Simple recursive + Greedy)

I will sell when the price is highest, and try to buy when the price is lowest. I am thinking about dynamic programming way, but it seems hard to me.

I cannot figure out any more efficient solution. Any suggestion, ideas, reference sources would be appreciated.