수박이 한 줄로 N개가 늘어져 있고, 그 중 i번째 수박의 맛은 k_i이다.

이때, 수박들은 k_i의 비내림차순(수박들은 k_i가 증가하거나 같은 순)으로 정렬되어 있다.

각 수박은 전체를 먹는데 a분이 걸리고, 수박의 겉만 핥는데에는 b분이 걸린다.
전체를 먹는 시간에는 수박의 겉을 핥는 시간도 포함되기 때문에 a>b를 항상 만족한다.

정올이는 총 T분 동안, 1번 수박부터 순서대로 수박들을 핥아보면서
이 수박 전체를 먹을지 말지 결정하여 전체를 먹은 수박들의 맛의 합이 최대가 되도록 하고 싶다. 이 값을 구해보자.

구체적으로, 어떤 수박을 b분 동안 핥으면서 정올이는 이 수박을 먹을 지 말지 결정한다.

먹기로 했다면 추가로 a-b분을 소모하여 전체 수박을 먹을 것이고, 그렇지 않다면 다음 수박으로 넘어갈 것이다.

꼭 모든 수박을 핥아볼 필요는 없다. 중간에 수박을 핥지 않고 넘어가는 것도 불가능하다.

즉, 현재 수박을 핥지도 먹지도 않았다면 이후 모든 수박을 핥지도 먹지도 않고 남겨두는 것은 가능하다.

수박 겉핥기 timer 1s memory 1024MB

수박 겉핥기 1s 1024MB