수박 겉핥기 timer 1초 memory 1024MB

수박이 한 줄로 N개가 늘어져 있고, 그 중 i번째 수박의 맛은 k_i이다. 이때, 수박들은 k_i가 증가하는 순으로 정렬되어 있다.

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

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

구체적으로, 어떤 수박을 b분 동안 핥으면서 정올이는 이 수박을 먹을 지 말지 결정한다. 먹기로 했다면 추가로 a-b분을 소모하여 전체 수박을 먹을 것이고, 그렇지 않다면 다음 수박으로 넘어갈 것이다.

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