롤러코스터 timer 1초 memory 64MB

소들이 롤러코스터를 만들고자 한다! 그들을 도와 가장 재미있는 롤러코스터를 설계해 보자.

롤러코스터의 가로 길이는 L(1≤L≤1,000)로 주어진다.

소들은 다양한 롤러 코스터 구성 요소를 함께 연결하는데

각 구성 요소의 끝 (마지막 구성 요소 제외)이 다음 구성 요소의 시작이 되도록 하여

0에서 시작하고 L에서 끝나는 롤러코드터를 만들고자 한다.

우리가 사용할 수 있는 구간은 총 N(1≤N≤10,000)개로 주어진다.

각 부품이 놓일 수 있는 가로 위치는 Xi로 정해져 있다.

또한 구간의 가로길이도 Wi로 주어져 있다.

또한 그 구간을 사용할 경우 드는 비용 Ci(1≤Ci≤1,000)와 재미있는 정도 Fi(1≤Fi≤1,000,000)도 주어져 있다.

소들은 롤러코스터를 만들기 위해 B(1≤B≤1,000)만큼의 예산을 마련해 놓았다.

구간들의 비용의 합이 예산을 넘지 않으면서 가장 재미도의 합이 가장 큰 롤러코스터를 설계해야한다.

물론 롤러코스터가 끊겨서는 안 된다.​