Games
(Main file name: games)

You have decided to come to a block party in Brooklyn, where there are n game booths G1, G2, ..., Gn from one end of the street to the other. You want to play all of the games in the order from G1 to  Gn without skipping any. The games are not free, and each game costs 1 token to play once. You can play a game as many times as you can, as long as you have enough tokens. Your pocket can hold at most T tokens, and the pocket is full in the beginning. After you finish one game Gi and before you start Gi+1, you will be refilled with K tokens. However, since the capacity of your pocket is T, any extra tokens will be wasted.

Some games are more fun than others. For each game Gi, you have an integer value Vi that indicates how fun this game is to you. For a game that you don't enjoy, the value can be negative. Note that you have to play each game at least once, even if the game is not fun to you. The total fun you gain from a game is the number of times you play the game times the fun value. You want to manage your tokens so that you gain the most fun from the games.


Input Formats

An input file for LP systems contains a fact of the form num(N), which specifies the number of games N (4 ≤ N ≤ 10), a fact of the form cap(T), which means that the capacity of your pocket is T (3 ≤ T ≤ 10), a fact of the form refill(K), which gives the number to tokens you receive after each game booth (0 < K ≤  T); N facts of the form fun(i,Vi), which indicates that the fun value of game Gi is Vi (1 ≤ i ≤ N, -10 ≤ Vi  ≤ 10).

An input file for Minizinc specifies the following constants: num, the number of games N; cap, the capacity of your pocket; refill, the number of tokens you receive after each game booth; fun, an array of fun values of the N games.

Output format

The output should contain exactly one fact of the form total_fun(V), where V is the maximum fun you can gain from playing these games.  For ASP systems, the output may consist of multiple answer sets, and only the final one is treated as a solution.

Samples


LP InputMinizinc InputOutput
num(4).
cap(5).
refill(2).
fun(1,4).
fun(2,1).
fun(3,2).
fun(4,3).
num = 4;
cap = 5;
refill = 2;
fun = [4,1,2,3];
total_fun(35).
num(4).
cap(5).
refill(2).
fun(1,4).
fun(2,-1).
fun(3,-2).
fun(4,3).
num = 4;
cap = 5;
refill = 2;
fun = [4,-1,-2,3];		total_fun(29).
num(5).
cap(3).
refill(2).
fun(1,4).
fun(2,1).
fun(3,-2).
fun(4,3).
fun(5,4).		num = 5;
cap = 3;
refill = 2;
fun = [4,1,-2,3,4];		total_fun(30).