Description

Cpg is visiting a city of dreams that has $n$ money trees. Each tree has already ripened. Cpg can stay in the city for $k$ days. Every day, each tree loses some coins that fall off and are not collected by Cpg. Each day, Cpg may cut down exactly one tree and obtain all the coins currently on that tree.

Formally, number the days as $t = 0, 1, \dots, k - 1$. Let the $i$-th tree initially have $m_i$ coins, and let it lose $b_i$ coins per day. If the $i$-th tree is cut on day $t$, the coins Cpg obtains from it are $\max(m_i - b_i \cdot t, 0)$. A tree, once cut, is no longer available on later days. Cpg may cut at most one tree per day, for up to $k$ days (or until all trees are cut).

Please help Cpg compute the maximum total number of coins he can obtain over these $k$ days.

Input Format

This problem contains multiple test cases within a single input file. There are at most $10$ test cases.

Each test case:

• The first line contains two integers $n, k$.
• The second line contains $n$ integers $m_i$, the number of coins on each tree when Cpg first sees them.
• The third line contains $n$ integers $b_i$, the number of coins each tree loses per day.

Input is terminated by a line containing 0 0.

Output Format

For each test case, output a single line with the maximum total number of coins Cpg can obtain in $k$ days.

3 3
10 20 30
4 5 6
4 3
20 30 40 50
2 7 6 5
0 0

47
104

Hint

Constraints

• For $100\%$ of the testdata, $1 \le n, k \le 10^3$, $1 \le m_i \le 10^5$, $1 \le b_i \le 10^3$.

Translated by ChatGPT 5