P1417 Cooking Plan

Thanks to your help, Mars suffered only minimal damage. But gw was too lazy to rebuild his home, so he built a spaceship and headed toward the distant planet Earth. Halfway through the journey, gw realized a serious problem: he was hungry. gw can still cook, so he took out stored food to fill his stomach. gw hopes to cook the most delicious food within $T$ time, but the way to calculate deliciousness is unusual, so the desperate gw is asking for your help.

There are $n$ ingredients. Each ingredient has three attributes, $a_i$, $b_i$, and $c_i$. If ingredient $i$ is completed at time $t$, you gain a deliciousness score of $a_i-t\times b_i$. Cooking ingredient $i$ takes $c_i$ time. As everyone knows, gw is not very good at cooking, so you need to design a cooking plan to maximize the deliciousness score. All cooking must be finished within time $T$.

The first line contains two positive integers $T$ and $n$, representing the time needed to reach Earth and the number of ingredients. - The next line contains $n$ integers, $a_i$. - The next line contains $n$ integers, $b_i$. - The next line contains $n$ integers, $c_i$.

Output the maximum deliciousness score.

- Constraints: - For $40\%$ of the testdata, $1 \le n \le 10$. - For $100\%$ of the testdata, $1 \le n \le 50$. - All numbers are less than $10^5$. - Source: adapted by tinylic. Translated by ChatGPT 5