맛있는 뷔페

뷔페에서 점심을 고르고 있다. 여러 요리가 있고, 원하는 대로 조합할 수 있다. 만두나 구운 감자처럼 비슷한 크기의 조각으로 나뉜 요리는 이산 요리라고 부르며, 조각 단위로만 가져갈 수 있다. 또 다른 요리는 자유롭게 양을 고를 수 있는 연속 요리다.

같은 요리라도 이미 먹은 양에 따라 느끼는 맛이 달라진다. 요리 $i$는 초기 맛 $t_i$와 맛 감소율 $\Delta t_i$를 가진다. 이산 요리에서 $n$번째 조각의 맛은 $t_i - (n-1)\Delta t_i$이고, 연속 요리에서 이미 $x$그램을 먹은 뒤 $dx$그램을 더 먹을 때 느끼는 맛은 $(t_i - x\Delta t_i)\,dx$이다. 따라서 이산 요리 $N$조각, 연속 요리 $X$그램을 먹었을 때 총 맛은 각각

$\sum_{n=1}^{N} (t_i - (n-1)\Delta t_i), \quad \int_0^X (t_i - x\Delta t_i)\,dx$

이다. 요리끼리의 궁합은 고려하지 않고, 한 끼의 총 맛은 각 요리에서 얻은 맛의 합으로 정의한다. 무게도 마찬가지다.

각 요리의 $t_i$와 $\Delta t_i$는 이미 구해 두었다. 이제 무게가 정확히 $w$그램인 한 끼에서 얻을 수 있는 최대 총 맛을 구하라.

하나의 테스트 케이스가 주어진다.

• 1행: 요리 수 $d$와 목표 무게 $w$ ($1 \le d \le 250$, $1 \le w \le 10000$)
• 다음 $d$행: 각 요리 설명
  • D $w_i$ $t_i$ $\Delta t_i$: 조각 하나가 $w_i$그램인 이산 요리
  • C $t_i$ $\Delta t_i$: 연속 요리

모든 $w_i$, $t_i$, $\Delta t_i$는 정수이며 $1 \le w_i \le 10000$, $0 \le t_i, \Delta t_i \le 10000$이다.

무게가 정확히 $w$그램인 식사에서 얻을 수 있는 최대 총 맛을 출력한다. 상대 오차 또는 절대 오차 $10^{-6}$ 이내여야 한다. 정확히 $w$그램을 만들 수 없으면 impossible을 출력한다.