Problem Description

There are $n$ different types of cards. For the $i$-th type, its base value is $v_i$, and there are $a_i$ cards of this type.

You need to choose exactly $X$ cards from these cards to form your own deck.

For the same type of card, as you choose more of them, the value of later cards will decrease. Specifically, if you have already chosen $k$ cards of a type with base value $v$, then the value of the next card of this type is:

$\lfloor x \rfloor$ means taking the floor of $x$, i.e., the largest integer that does not exceed $x$.

That is:

• When choosing the $1$-st card of this type, its value is $\left\lfloor \frac{v}{1} \right\rfloor = v$;
• When choosing the $2$-nd card, its value is $\left\lfloor \frac{v}{2} \right\rfloor$;
• When choosing the $3$-rd card, its value is $\left\lfloor \frac{v}{3} \right\rfloor$;
• And so on.

For each type of card, you can choose at most $a_i$ cards.

Now, please compute: when choosing exactly $X$ cards, what is the maximum total value you can obtain.

Input Format

The input consists of three lines.

The first line contains two integers $n, X$, representing the number of card types and the total number of cards that need to be chosen.

The second line contains $n$ integers $v_1, v_2, \dots, v_n$, representing the base value of each card type.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$, representing how many cards are available for each type.

Output Format

Output one line with one integer, representing the maximum total value.

6 6
1 1 2 3 4 5
1 2 1 2 3 4

18

Hint

Sample Explanation

After expanding the values of all possible single cards, we get:

• Type $1$ can contribute: $1$.
• Type $2$ can contribute: $1, 0$.
• Type $3$ can contribute: $2$.
• Type $4$ can contribute: $3, 1$.
• Type $5$ can contribute: $4, 2, 1$.
• Type $6$ can contribute: $5, 2, 1, 1$.

Choose the largest $6$ values among them: $5, 4, 3, 2, 2, 2$. Their sum is $5+4+3+2+2+2 = 18$, so the answer is $18$.

Constraints and Notes for Test Cases

For $50\%$ of the test cases, $1 \le n, X \le 5000$.

For all test cases, it holds that $1 \le n \le 2 \times 10^5$, $0 \le X, a_i \le 2 \times 10^5$, and $0 \le v_i \le 10^9$.

It is guaranteed that the total number of cards is at least $X$.

Translated by ChatGPT 5