시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB198366549333.424%

문제

최재현은 지지부진한 알앤이 진도에 분노해서, 구재현의 싸대기에 잘 익은 김치를 던지려고 한다.

물론 김치를 만드는 것이 쉬운 일은 아니기 때문에, 갈수록 추워지는 가을날 최재현은 남도에 있는 한 김치 명장을 찾아갔다.

김치 명장이 말한 "좋은 김치"의 조건은 :

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

최재현은 이 말이 잘 와닿지 않는지, 계속 질문을 던졌다. 다행인지 불행인지, 김치 명장은 컴퓨터 공학과를 전공한 실력 있는 프로그래머이다. 때문에 김치의 맛을 조금 더 엄밀하게 정의했다.

  • 김치의 맛은, (숙성 시간) * (김치를 꺼낼 때의 온도) + (김치를 넣은 날 가치) 로 정의된다. 숙성 시간은, (김치를 꺼낸 날짜 - 김치를 넣은 날짜) 이며, 숙성 시간이 0일 수도 있다.
  • 겨울이 오기 때문에, 김치를 꺼낼 때의 온도는 감소한다. (Ti >= Ti+1)

하지만 최재현은 그렇게 시간이 많지 않고, 솔직히 말해서 알앤이 파트너에게 묵은지로 싸대기를 때리는 건 좀 나쁜 거 같다고 생각해서, 숙성 시간이 D 이하인 범위 안에서 재현이에게 싸대기를 때리려고 한다. 

재현이에게는 매일의 온도와 장독대의 가치가 주어진다. 재현이가 던질 수 있는 가장 맛있는 김치싸대기의 값은 얼마가 될수 있을까?

입력

첫 번째 줄에 날짜의 수와 시간 제한 N, D가 주어진다. (1 ≤ D ≤ N ≤ 100,000)

두 번째 줄에 온도 Ti가 주어진다. N-1 이하의 정수 i에 대해서 Ti >= Ti+1을 만족하며, 109 이하의 자연수이다.

세 번째 줄에 가치 Vi가 주어진다. 109 이하의 자연수이다.

출력

가장 맛있는 김치싸대기의 값을 출력하라.

예제 입력 1

4 4
23 22 21 20
20 40 30 50

예제 출력 1

80

예제 입력 2

4 1
23 22 21 20
20 40 30 50

예제 출력 2

61

출처