철기는 바게트 빵을 너무나 좋아한다. 어느 날 철기는 정말 특이한 바게트 빵을 사게 되었다. 일반적인 바게트 빵과 마찬가지로 철기가 새로 산 바게트 빵은 기다란 모양을 띄고 있다. 그러나 이 바게트 빵은 정확히 직사각형의 형태로 되어 있다.

바게트 빵의 맨 위쪽을 0 이라고 하고, 맨 오른쪽을 L 이라고 하자. 여기서 위쪽에서 a만큼 떨어진 위치부터 b (a < b)만큼 떨어진 위치까지의 연속된 구간을 잘라서 먹게 되면 D 만큼의 맛을 느낄 수 있을 것으로 예상한다.

단순히 한 부분을 자르는 게 아니라 여러 부분을 자를 수 있으나, 자르고자 하는 위치가 겹치는 경우(예를 들어 2부터 4까지의 구간을 자르고자 결정하면 3부터 5까지의 구간)는 자를 수 없게 된다. 하지만 2부터 4까지의 구간을 자르려고 결정 했을 경우 4부터 8까지의 구간이 존재할 경우는 4부터 8까지의 구간 역시 자를 수 있다고 간주한다.

철기가 자르고자 하는 N 개의 구간이 주어지고, 각 구간마다 느낄 수 있을 것이라고 예상 되는 맛의 기대치가 주어졌을 때, 구간을 겹치지 않고 잘라진 구간의 맛의 기대치 합이 최대화가 되게끔 바게트를 자르는 프로그램을 작성하라.

#2174 upload 5 done 1 how_to_reg 1

맛있는 바게트 timer 1s memory - MB

#2174

맛있는 바게트 1s - MB