B. 푸짐한 뷔페

당신은 뷔페에서 점심을 사 먹고 있다. 다양한 요리가 준비되어 있고, 마음껏 조합해 먹을 수 있다. 만두나 구운 감자처럼 대략 같은 크기의 조각으로 이루어진 요리도 있는데, 이런 요리는 정수 개의 조각만 집을 수 있다(쪼개는 것은 허용되지 않는다). 이를 “이산 요리”라고 부르자. 차치키나 으깬 감자 같은 다른 요리는 유동적이어서 실수 값(re\(al-va\)lued)의 임의의 양을 담을 수 있다. 이 두 번째 유형을 “연속 요리”라고 부르자. 물론 요리마다 좋아하는 정도가 다르지만, 어떤 요리를 얼마나 좋아하는지는 이미 그 요리를 얼마나 먹었는지에도 달려 있다. 예를 들어 평소에는 감자보다 만두를 좋아하더라도, 이미 만두를 열 개 먹었다면 만두보다 감자를 선호할 수 있다. 이를 모델링하기 위해 각 요리 \(i\)에는 초기 맛 \(t_{i}\)와 맛의 감소율 ∆\(t_{i}\)가 있다. 이산 요리의 경우, 그 요리의 \(n^{th}\)번째 조각을 먹을 때 경험하는 맛은 \(t_{i}\) −(\(n - 1\))∆\(t_{i}\)이다. 연속 요리의 경우, 이미 \(x\)그램을 먹은 뒤 극소량 \(dx\)그램을 먹을 때 경험하는 맛은 (\(ti - x\)∆\(ti\))\(dx\)이다. 즉, 이산 요리 \(N\)조각을 먹거나 연속 요리 \(X\)그램을 먹을 때 경험하는 총 맛은 각각 다음과 같다. \(N\) X \(n=1\) (\(t_{i}\) −(\(n - 1\))∆\(t_{i}\)) 그리고 Z _{X} (\(t_{i} - x\)∆\(t_{i}\))\(dx\) 단순화를 위해 요리들의 궁합은 고려하지 않으며, 한 끼 식사에서 경험하는 총 맛은 식사에 포함된 각 요리의 총 맛의 합으로 정의한다(식사의 무게도 마찬가지다. 뷔페에 음식 반입자는 없다!). 당신은 며칠에 걸친 공들인 조사 끝에 뷔페의 각 요리에 대한 수 \(ti\)와 ∆\(ti\)를 알아냈다. 남은 일은 무게 \(w\)인 식사에서 얻을 수 있는 최대 총 맛을 계산하는 것뿐이다. 서두르는 게 좋다. 곧 점심이 시작된다!

입력은 하나의 테스트 케이스로 이루어져 있다. 입력의 첫 줄에는 두 정수 \(d\)와 \(w\) (\(1 \le d \le 250\), \(1 \le w \le 10\,000\))가 주어지며, \(d\)는 뷔페의 서로 다른 요리 수이고 \(w\)는 원하는 식사의 총무게(그램)이다. 이어서 \(d\)개의 줄이 오는데, 그중 \(i^{th}\)번째 줄은 \(i^{th}\)번째 요리를 설명한다. 각 요리 설명은 다음 두 형식 중 하나이다.

• “D \(wi\) \(ti\) ∆\(ti\)” 형식의 설명은 이것이 각 조각의 무게가 \(wi\)그램이고 초기 맛이 \(ti\), 맛의 감소율이 ∆\(ti\)인 이산 요리임을 나타낸다.

• “C \(t_{i}\) ∆\(t_{i}\)” 형식의 설명은 이것이 초기 맛이 \(ti\), 맛의 감소율이 ∆\(ti\)인 연속 요리임을 나타낸다. 수 \(wi\), \(ti\), ∆\(ti\)는 \(1 \le wi \le 10\,000\)과 \(0 \le ti\), ∆\(ti \le 10\,000\)을 만족하는 정수이다.

준비된 요리들로 무게 \(w\)인 식사를 만들 때 가능한 최대 총 맛을 출력한다. 답의 상대 또는 절대 오차는 \(10^{−}^{6}\) 이하여야 한다. 준비된 요리들로 총무게가 정확히 \(w\)인 식사를 만드는 것이 불가능하면 impossible을 출력한다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2014