Nhà bé MofK có ~n~ khu vườn, mỗi khu vườn trồng một trong ~k~ loại quả: khu vườn thứ ~i~ trồng loại quả ~t_i~ và có ~a_i~ quả.

Để có nguyên liệu làm bánh, mẹ bé MofK giao cho bé đi hái quả. MofK sẽ chọn một đoạn ~[l..r]~ và hái hết quả ở những khu vườn đó. Mỗi bánh cần nguyên liệu là một quả mỗi loại, vì vậy nếu MofK lần lượt hái được ~x_1, x_2, \ldots, x_k~ quả mỗi loại, mẹ sẽ làm được ~\min(x_1, x_2, \ldots, x_k)~ bánh, số quả còn dư sẽ thưởng cho bé MofK. Nói cách khác, bé MofK sẽ được ăn ~x_1 + x_2 + \ldots + x_k - k \cdot \min(x_1, x_2, \ldots, x_k)~ quả.

Hãy giúp bé MofK chọn đoạn ~[l..r]~ để được ăn nhiều quả nhất nhé!

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~1 \le n, k \le 3 \cdot 10^5~) — số khu vườn và số loại quả được trồng.

Dòng tiếp theo chứa ~n~ số nguyên dương ~t_1, t_2, \ldots, t_n~ (~1 \le t_i \le k~) — loại quả được trồng trong khu vườn thứ ~i~.

Dòng cuối cùng chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — số lượng quả được trồng trong khu vườn thứ ~i~.

Output

In ra một số nguyên dương duy nhất: số lượng quả lớn nhất mà bé MofK có thể được ăn.

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

Ở test mẫu đầu tiên, ta có thể chọn đoạn ~[1, 3]~; khi đó, số lượng quả MofK hái được lần lượt là ~[3, 9, 0]~, vì vậy số lượng quả còn lại bé MofK được ăn là ~3 + 9 + 0 - 3 \cdot 0 = 12~.

Ở test mẫu thứ hai, vì chỉ có một loại quả duy nhất nên toàn bộ số quả mà MofK hái được sẽ đem đi làm bánh, và MofK sẽ không có quả nào để ăn. :(