Dynamic Programming: Two Parameters

ID 18786. Pascal's triangle

Examples

ID 23407. Minimum path in table

ID 23412. Parentheses recovery

Examples

ID 33142. Knight's move_1

Examples

ID 33143. Knight's move - 2

Given a rectangular board N × M (N rows and M columns). In the upper left corner is a chess knight, which must be moved to the lower right corner of the board. In this case, the horse can only walk as shown in the figure:

Examples

ID 38286. Need more gold

Petya loves computer games very much. Recently, he discovered an interesting role-playing game on the Internet. Controlling the hero, you need to look for magical artifacts and get gold.

Unfortunately, the very first quest in the game put Petya in a dead end. After completing the task, he received n magical artifacts that can be used to get gold. For each artifact its value is known, for the i -th artifact it is equal to w_i . Artifacts can be activated to get gold. Each artifact can only be activated once. Petya can activate artifacts in any order.

The hero controlled by Petya has magic power, initially it is equal to zero. There are two ways to activate an artifact: through magic and through force. If you activate an artifact with a value of w using magic, then the hero's magic power is increased by w . If you activate an artifact with a value of w using force, then the hero receives xw gold coins, where x — the hero's magic power at the moment the artifact is activated.

For example, if the hero Petit received 4 artifacts with values ​​1, 1, 2 and 2, then you can get 9 gold coins by proceeding as follows. First, you need to use magic to activate one artifact each with a value of 1 and 2. After that, the hero's magic power is 3, now you can activate the remaining artifacts using strength and get 3 and 6 gold coins, respectively.

Help Petya determine the maximum number of gold coins he can get by activating the artifacts in the correct order in the best possible way.

Input
The first line of the input contains a single number n — number of magic artifacts ( 1 ≤ n ≤ 100 ).

The second line of the input contains n numbers w₁ , w₂ , ..., w_n — artifact values ​​( 1 ≤ w_i ≤ 100 ).

Imprint
Print the maximum possible number of gold coins that can be obtained with the help of magical artifacts.

Examples

ID 38296. Daily Rewards

Misha installed a new game "Memtest 2k17" on his phone. It provides daily rewards for visiting. Rewards come in n levels. The type of reward depends on the reward for the previous day, namely:

if the player did not visit the game the previous day, then for today's visit he will receive a level 1 reward;
if a player entered the game the previous day and received a level k reward ( k ≠ n ), then for today's visit he will receive a level k reward + 1 ;
if a player entered the game the previous day and received a level n reward, then for today's visit he will receive a level 1 reward.
At the Forum for Cool Programmers, Misha found out that the rewards of each of the levels are respectively a 1 , a 2 , ..., a n gold coins.
In m days, there will be a Memtest 2k17 tournament, for which Misha wants to collect as many gold coins as possible. Help him plan visits to the game during the m days left before the tournament. Find the most gold coins he can get from daily rewards during this period. We can assume that the game was installed on the first of these m days, that is, Misha has never logged into it before.

Input
The first line of the input contains natural numbers n and m ( 1 ≤ n , m ≤ 1000 ) — number of reward levels and days before the tournament.

The second line of the input contains n integers a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), where a i — the value of the i-th level reward in gold coins.

Imprint
Print one natural number — the most gold coins that Misha can get before the tournament.

Note
In the first test from the example, it is profitable for Misha to enter the game every day. Then he will get 1 + 2 + 4 = 7 gold coins.

In the second test from the example, it is profitable for Misha to enter the game on the first and third days, receiving 4 coins on each of them, then he will receive 8 coins in total.
 

Examples

ID 38515. Burgers at McDuck's

The popular fast food chain «McDuck's» opened a new branch in Berland. The restaurant has k stoves. To cook a burger, you need to fry a patty for a minute on one of the stoves, so a restaurant can cook no more than k burgers per minute.

It is known that in «McDuck's» n clients will come. The i-th of them will arrive at time t_i, order x_i burgers and be ready to pay c_i burles for them. Each client is ready to wait for an order for w minutes, and if w minutes after arrival he has not received x_i burgers, he will not pay anything. At the same time, each client is ready to receive only fresh burgers, that is, only those for which the burgers were fried not earlier than the time t_i. Due to such complex requirements, the restaurant will not always be able to fulfill all the orders of all customers.

The restaurant managers were interested in the maximum profit McDuck's could make. Help them answer this difficult question. We can assume that no money is spent on cooking burgers.

Input
The first line contains three integers n, k and w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — the number of clients, the number of plates and the waiting time for the client, respectively.

The next n lines contain descriptions of clients, consisting of three integers — t_i, x_i, c_i (1 ≤ t_i, x_i sub>, c_i ≤ 10⁹) — the time (in minutes) of arrival of the i-th customer, the number of burgers he will order and the number of burles he is willing to pay, respectively. Clients are listed in ascending order of arrival time, i.e. for any i > 1 it is true that t_i−1 ≤ t_i.

Imprint
In a single line print a single number — maximum restaurant profit.

Note
In the first test example, the first patty can be fried at time 0, and then at time 1 it will be ready and can be served in a burger to the first client. At time 1, you can put another patty to fry, it will be ready at time 2 and can be served in a burger to the second client.
 

Examples

ID 40064. Sequences of length N

How many integer sequences of length N, A = (A₁,…,A_N), satisfy all given below conditions?
1) 1 <= A_i <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Input
The input is a string containing three integers N, M (1 <= N, M <= 50), K (N <= K <= NM).

Imprint
Output the answer to the problem.
 

Examples

2 3 4

6