김치

가을부터 겨울까지 이어지는 $N$일 동안 장독대에서 김치를 익힌다. 김치는 어느 하루에 한 번 담그고, 담근 날 또는 그 뒤의 어느 하루에 한 번 꺼낸다.

김치 명장이 말하는 좋은 김치의 조건은 다음과 같다.

• 숙성 시간이 길수록 김치의 맛은 좋아진다.
• 추운 날에는 김치가 얼기 때문에, 꺼낼 때의 온도가 높을수록 김치의 맛은 좋아진다.
• 김치를 담근 날 장독대의 가치가 맛에 영향을 준다.

이 조건을 수식으로 정리하면 다음과 같다. $i$번째 날에 담가서 $j$번째 날에 꺼내면 ($i \le j$) 숙성 시간은 $j - i$이고, 숙성 시간은 $0$일 수도 있다. 이때 김치의 맛은

$(j - i) \times T_j + V_i$

이다. $T_j$는 $j$번째 날의 온도, $V_i$는 $i$번째 날 장독대의 가치이다. 겨울이 다가오면서 온도는 떨어지기만 하므로 모든 $i$에 대해 $T_i \ge T_{i+1}$이 성립한다.

너무 오래 묵힌 김치는 쓰지 않으므로 숙성 시간은 $D$ 이하여야 한다.

매일의 온도와 장독대의 가치가 주어질 때, 얻을 수 있는 김치 맛의 최댓값을 구하라.

첫째 줄에 날짜의 수 $N$과 숙성 시간의 상한 $D$가 주어진다. ($1 \le D \le N \le 100000$)

둘째 줄에 온도 $T_1, T_2, \dots, T_N$이 주어진다. 각 $T_i$는 $10^9$ 이하의 자연수이고, $1 \le i \le N-1$인 모든 $i$에 대해 $T_i \ge T_{i+1}$을 만족한다.

셋째 줄에 장독대의 가치 $V_1, V_2, \dots, V_N$이 주어진다. 각 $V_i$는 $10^9$ 이하의 자연수이다.

김치 맛의 최댓값을 한 줄에 출력한다.