Problem Description

Xiao Piqiu, who is in college, loves the game League of Legends, but he plays very poorly, so online players jokingly call him an “elementary school kid”.

Now, Xiao Piqiu finally cannot stand the ridicule anymore and decides to become stronger. His way to become stronger is: buying skins.

Xiao Piqiu can only play $N$ champions, so he only plans to buy skins for these $N$ champions, and he decides that in the future he will only play champions that have skins.

Among these $N$ champions, the $i$-th champion has $K_i$ skins, and the price is $C_i$ Q-coins per skin (skins of the same champion have the same price).

To make himself look more impressive, Xiao Piqiu decides to show his skins to his classmates. The idea is: for each champion that has skins, randomly choose one skin to show.

For example, Xiao Piqiu has $5$ champions, and these $5$ champions have $0, 0, 3, 2, 4$ skins respectively. Then Xiao Piqiu has $3 \times 2 \times 4 = 24$ ways to show them.

Now, Xiao Piqiu wants the number of his showing strategies to be at least $M$. How much money does he need to spend at least?

Input Format

The first line contains two integers $N, M$.

The second line contains $N$ integers, representing the number of skins for each champion $K_i$.

The third line contains $N$ integers, representing the price of each champion’s skins $C_i$.

Output Format

One integer, representing the minimum cost for Xiao Piqiu to reach the goal.

3 24
4 4 4
2 2 2

18

Hint

Sample Explanation

Each champion has $4$ skins, and each skin costs $2$ Q-coins. Then for each champion, buy $3$ skins: $3 \times 3 \times 3 \ge 24$. The total cost is $6 \times 3$ Q-coins.

Constraints

There are $10$ test cases in total. For the $i$-th test case: $N \le \max(5, \log_2^4{i})$.

For $100\%$ of the testdata: $M \le 10^{17}, 1 \le K_i \le 10, 1 \le C_i \le 199$. A solution is guaranteed to exist.

Translated by ChatGPT 5