17108번 - 파이의 왕 김파이 언어 제한번외

우리는 파이를 좋아한다. 우리가 가장 좋아하는 수도 pi이고, 우리가 가장 좋아하는 브라우저도 파이어폭스, 우리가 가장 좋아하는 포켓몬도 파이리, 우리가 가장 좋아하는 철학자도 파울 카를 파이어아벤트, 우리가 가장 좋아하는 솔리테어 게임도 스파이더, 우리가 가장 좋아하는 RPG게임도 파이널 판타지, 우리가 가장 좋아하는 격투게임은 굉장히 많고, 우리가 가장 좋아하는 카드 게임도 슬레이 더 스파이어, 우리가 가장 좋아하는 LOL 서포터도 파이크, 우리가 가장 좋아하는 미사일도 스파이크, 우리가 가장 좋아하는 해리 포터 마법도 스투페파이, 우리가 가장 좋아하는 악마도 파이몬, 우리가 가장 좋아하는 코미디도 몬티 파이선, 우리가 가장 좋아하는 악기도 파이프오르간이다. 물론 우리가 가장 좋아하는 프로그래밍 언어는 말할 것도 없이 Delphi이다. 아쉽게도 델파이는 BOJ에 없어서 이 사이트에서는 우리가 그 다음으로 좋아하는 Pike를 쓴다.

우리는 긴 직육면체 모양의 사과파이 N개를 상자에 담으려고 한다. (이 상자는 소나무로 만들어졌는데, 소나무는 영어로 pine이다.) 사과파이의 너비와 높이는 상자와 같아서, 사과파이 몇 개를 상자에 담을 때 길이의 총합이 상자의 길이보다 작거나 같아야 한다. 그리고 사과파이에 번호가 붙어 있어서 한 상자에 담는 사과파이의 번호는 연속해야 한다.

그런데 특정 사과파이들은 길이가 1인데 성분이 특이해서, 다른 사과파이와 같은 상자에 담으면 상해버린다. 그래서 그 사과파이를 상자에 담을 경우 다른 사과파이가 그 상자에 들어 있으면 안 된다.

우리는 길이가 모두 같은 상자를 사오려고 하는데, 사올 수 있는 상자의 길이는 L 이상 R 이하의 정수이고, 길이가 x인 상자 하나의 가격은 x원이다. 상자의 길이를 얼마로 잡아야 총 가격이 최소화되는지 우리는 감을 못 잡고 있다.

불쌍한 김우리를 도와 주자.

먼저 N, L, R이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ L ≤ R ≤ 10,000)

그 다음부터는 첫 몇 개의 사과파이의 정보가 차례로 주어진다. 특이한 사과파이일 경우 0, 아닐 경우 파이의 길이가 주어진다. 입력으로 주어지지 않는 사과파이는 모두 특이한 사과파이이다. (1 ≤ 길이 ≤ L)

입력으로 들어오는 모든 수는 정수이다.

상자를 구입하는 최소 비용을 출력한다.