Background

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.

Problem Description

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$.

Input Format

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 Format

Output the maximum deliciousness score.

74 1
502
2
47

408

Hint

• 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