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