[Solution] Story of Seasons Round F 2022 - Kick Start 2022 Solution

Problem

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 X$X$ seeds each day. In the beginning, you have N$N$ kinds of vegetable seeds. The number of seeds of the i$i$-th kind of vegetable is Qi${\mathbf{Q}}_{\mathbf{i}}$, and each seed of this kind needs Li${\mathbf{L}}_{\mathbf{i}}$ days to mature from the day it is planted. Once it matures, you can sell it for Vi${\mathbf{V}}_{\mathbf{i}}$ 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 D$D$ 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.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
The first line of each test case contains three integers D$D$, N$N$, and X$X$: 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 N$N$ lines describe the seeds. The i$i$-th line contains three integers Qi${\mathbf{Q}}_{\mathbf{i}}$, Li${\mathbf{L}}_{\mathbf{i}}$, and Vi${\mathbf{V}}_{\mathbf{i}}$: 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 #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the maximum amount of money you can earn by optimizing your farming plan.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤Vi≤106$1\le {\mathbf{V}}_{\mathbf{i}}\le {10}^6$, for all i$i$.
1≤Li≤D$1\le {\mathbf{L}}_{\mathbf{i}}\le \mathbf{D}$, for all i$i$.

Test Set 1

Time limit: 20 seconds.
2≤D≤1000$2\le \mathbf{D}\le 1000$.
1≤N≤15$1\le \mathbf{N}\le 15$.
X=1$\mathbf{X}=1$.
Qi=1${\mathbf{Q}}_{\mathbf{i}}=1$, for all i$i$.

Test Set 2

Time limit: 60 seconds.
2≤D≤105$2\le \mathbf{D}\le {10}^5$.
1≤N≤105$1\le \mathbf{N}\le {10}^5$.
1≤X≤109$1\le \mathbf{X}\le {10}^9$.
1≤Qi≤106$1\le {\mathbf{Q}}_{\mathbf{i}}\le {10}^6$, for all i$i$.

Test Set 3

Time limit: 60 seconds.
2≤D≤1012$2\le \mathbf{D}\le {10}^{12}$.
1≤N≤105$1\le \mathbf{N}\le {10}^5$.
1≤X≤109$1\le \mathbf{X}\le {10}^9$.
1≤Qi≤106$1\le {\mathbf{Q}}_{\mathbf{i}}\le {10}^6$, for all i$i$.
D×X≤1018$\mathbf{D}\times \mathbf{X}\le {10}^{18}$.In Sample Case #1, there are 

D=5$\mathbf{D}=5$ days, N=4$\mathbf{N}=4$ kinds of vegetables and you can plant at most X=1$\mathbf{X}=1$ seed each day. Supposing the 4$4$ kinds of vegetables are spinach, pumpkin, carrot and cabbage, we have that

• Spinach needs 2$2$ days to grow, each matured one is worth 3$3$ dollars, and you start with 1$1$ spinach seed.
• Pumpkin needs 3$3$ days to grow, each matured one is worth 10$10$ dollars, and you start with 1$1$ pumpkin seed.
• Carrot needs 4$4$ days to grow, each matured one is worth 5$5$ dollars, and you start with 1$1$ carrot seed.
• Cabbage needs 2$2$ days to grow, each matured one is worth 2$2$ dollars, and you start with 1$1$ cabbage seed.

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

• Day 1: plant 1$1$ carrot
• Day 2: plant 1$1$ pumpkin
• Day 3: plant 1$1$ spinach
• Day 4: plant 1$1$ 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: 1$1$ spinach, 1$1$ pumpkin and 1$1$ carrot harvested, you earn 18$18$ dollars

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