## Story of Seasons solution kickstart

You are a super farmer with some vegetable seeds and an infinitely large farm. In fact, not only are you a farmer, but you are also secretly a super programmer! As a super programmer, you hope to maximize the profit of your farming using your programming skills.

Since your daily energy is limited, you can plant at most XX seeds each day. In the beginning, you have NN kinds of vegetable seeds. The number of seeds of the ii-th kind of vegetable is QiQi, and each seed of this kind needs LiLi days to mature from the day it is planted. Once it matures, you can sell it for ViVi dollars. Assume that no energy or time is required for harvesting and selling vegetables. Also, your farm is infinitely large so the growing vegetables do not crowd out each other.

Notice that although the area of your farm is infinite, the number of days that you can plant seeds is limited. The warm season only lasts DD days, and after that, the harsh winter comes. Any vegetable that has not matured yet will die immediately and cannot be turned into profit. The remaining seeds that were not planted cannot be turned into profit either.

As a super farmer and a super programmer, you want to come up with a perfect planting plan that will maximize your profit. Find the total amount of profit you will earn.

## Story of Seasons solution kickstart

### Input

The first line of the input gives the number of test cases, TTTT test cases follow.
The first line of each test case contains three integers DDNN, and XX: the number of days of the warm season, the number of kinds of vegetable seeds you have to start with, and the maximum number of seeds you can plant each day, respectively.
The next NN lines describe the seeds. The ii-th line contains three integers QiQiLiLi, and ViVi: the quantity of this kind of seed, the number of days it needs to mature, and the value of each matured plant, respectively.

### Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the maximum amount of money you can earn by optimizing your farming plan.

### Limits

Memory limit: 1 GB.
1T1001≤T≤100.
1Vi1061≤Vi≤106, for all ii.
1LiD1≤Li≤D, for all ii.

## Story of Seasons solution kickstart

Time limit: 20 seconds.
2D10002≤D≤1000.
1N151≤N≤15.
X=1X=1.
Qi=1Qi=1, for all ii.

#### Test Set 2

Time limit: 60 seconds.
2D1052≤D≤105.
1N1051≤N≤105.
1X1091≤X≤109.
1Qi1061≤Qi≤106, for all ii.

#### Test Set 3

Time limit: 60 seconds.
2D10122≤D≤1012.
1N1051≤N≤105.
1X1091≤X≤109.
1Qi1061≤Qi≤106, for all ii.
D×X1018D×X≤1018.

## Story of Seasons solution kickstart

Note: there are additional samples that are not run on submissions down below.

Sample Input
2
5 4 1
1 2 3
1 3 10
1 4 5
1 2 2
5 1 1
1 1 1

Sample Output
Case #1: 18
Case #2: 1


In Sample Case #1, there are D=5D=5 days, N=4N=4 kinds of vegetables and you can plant at most X=1X=1 seed each day. Supposing the 44 kinds of vegetables are spinach, pumpkin, carrot and cabbage, we have that

• Spinach needs 22 days to grow, each matured one is worth 33 dollars, and you start with 11 spinach seed.
• Pumpkin needs 33 days to grow, each matured one is worth 1010 dollars, and you start with 11 pumpkin seed.
• Carrot needs 44 days to grow, each matured one is worth 55 dollars, and you start with 11 carrot seed.
• Cabbage needs 22 days to grow, each matured one is worth 22 dollars, and you start with 11 cabbage seed.

The maximum profit you can make is 1818 dollars. One of the schedules you can use is:

• Day 1: plant 11 carrot
• Day 2: plant 11 pumpkin
• Day 3: plant 11 spinach
• Day 4: plant 11 cabbage
• Day 5: do nothing

And with this schedule, the vegetables will mature and turn into profit as following days:

• Day 1: nothing harvested
• Day 2: nothing harvested
• Day 3: nothing harvested
• Day 4: nothing harvested
• Day 5: 11 spinach, 11 pumpkin and 11 carrot harvested, you earn 1818 dollars

Note that the cabbage is supposed to mature on day 66, but it will actually die because of the winter.

## Story of Seasons solution kickstart

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input
1
5 3 4
5 2 3
2 3 10
2 4 5

Sample Output
Case #1: 45

In Additional Sample Case #1, there are D=5D=5 days, N=3N=3 kinds of vegetables and you can plant at most X=4X=4 seeds each day. Supposing the 33 kinds of vegetables are spinach, pumpkin and carrot, we have that

• Spinach needs 22 days to grow, each matured one is worth 33 dollars, and you start with 55 spinach seeds.
• Pumpkin needs 33 days to grow, each matured one is worth 1010 dollars, and you start with 22 pumpkin seeds.
• Carrot needs 44 days to grow, each matured one is worth 55 dollars, and you start with 22 carrot seeds.

The maximum profit you can make is 4545 dollars. One of the schedules you can use is:

• Day 1: plant 11 pumpkin, 22 carrots and 11 spinach
• Day 2: plant 22 spinach and 11 pumpkin
• Day 3: plant 22 spinach
• Day 4: do nothing
• Day 5: do nothing

And with this schedule, the vegetables will mature and turn into profit as following days:

• Day 1: nothing harvested
• Day 2: nothing harvested
• Day 3: 11 spinach harvested, you earn 33 dollars
• Day 4: 22 spinach and 11 pumpkin harvested, you earn 1616 dollars
• Day 5: 22 spinach, 11 pumpkin and 22 carrots harvested, you earn 2626 dollars