Little MofK has ~n~ gardens, each garden grows one of ~k~ types of fruits: the ~i~-th garden grows fruit type ~t_i~ and has ~a_i~ fruits.

To make cakes, MofK's mother sends him to harvest fruits. MofK will choose a segment ~[l..r]~ and pick all the fruits in those gardens. Each cake requires one fruit of each type, so if MofK picks ~x_1, x_2, \ldots, x_k~ fruits of each type, his mother can make ~\min(x_1, x_2, \ldots, x_k)~ cakes, and the remaining fruits will be given to MofK. In other words, MofK will eat ~x_1 + x_2 + \ldots + x_k - k \cdot \min(x_1, x_2, \ldots, x_k)~ fruits.

Help MofK choose the segment ~[l..r]~ to eat as many fruits as possible!

Input

The first line contains two positive integers ~n~ and ~k~ (~1 \le n, k \le 3 \cdot 10^5~) — the number of gardens and the number of fruit types.

The next line contains ~n~ positive integers ~t_1, t_2, \ldots, t_n~ (~1 \le t_i \le k~) — the type of fruit grown in the ~i~-th garden.

The last line contains ~n~ positive integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — the number of fruits grown in the ~i~-th garden.

Output

Print a single positive integer: the maximum number of fruits that MofK can be given.

Scoring

Sample Input 1

4 3
2 1 2 3
6 3 3 4

Sample Output 1

12

Sample Input 2

4 1
1 1 1 1
3 2 6 2

Sample Output 2

0

Notes

In the first sample test, we can choose the segment ~[1, 3]~; then, the number of fruits MofK picks are ~[3, 9, 0]~, so the number of fruits that MofK can eat is ~3 + 9 + 0 - 3 \cdot 0 = 12~.

In the second sample test, since there is only one type of fruit, all the fruits that MofK picks will be used to make cakes, and MofK will not have any fruits to eat. :(