용액 혼합

Yokohama Yellow, 줄여서 YY라는 화학물질로 실험을 준비하려고 한다. YY 수용액이 든 용기가 여러 개 있다. YY는 각 용액에 고르게 녹아 있지만, 용기마다 농도는 다를 수 있다. 여러 용기에서 임의의 양만큼 용액을 덜어 섞어서, 정해진 총량의 새 용액을 만든다.

이상적으로는 혼합 용액에 목표량의 YY가 들어 있어야 한다. 하지만 문제가 있다. 각 용기의 용액량은 정확히 알지만, 각 용액에 들어 있는 YY의 양은 일정 범위 안에 있다고만 보장된다. 이 불확실성 때문에 혼합 용액의 YY 양을 목표량에 정확히 맞추기는 어렵다. 그래도 목표량과의 차이인 오차가 일정 한계를 넘지 않도록 보장할 수 있다.

정확히 말하면, 혼합 용액의 목표 YY 양을 $y_t$ mg, 실제 YY 양을 $y_a$ mg라 하자. 용기에서 덜어낸 용액량이 주어지면 $y_a$는 일정 범위 안에 있다고 보장된다. 최대 오차는 $y_a$가 이 범위에서 변할 때 $|y_a - y_t|$의 최댓값이다.

각 용기에서 덜어내는 비율은 자유롭게 정할 수 있고, 전체 합이 정해진 총량과 같기만 하면 된다. 이때 달성 가능한 최대 오차의 최솟값을 구하라.

입력은 다음 형식으로 주어지는 하나의 테스트 케이스이다.

$n$ $s$ $c$

$a_1$ $l_1$ $r_1$

$\vdots$

$a_n$ $l_n$ $r_n$

첫 줄에는 세 정수 $n$, $s$, $c$가 주어지며, $1 \le n \le 1000$, $1 \le s \le 10^5$, $0 \le c \le M$을 만족한다. 여기서 $M = 10^4$이다. $n$은 용기의 개수이고, $s$는 혼합 용액의 총량(mg)이다. 목표 YY 양은 $\frac{c}{M}s$ mg이다.

이어지는 $n$개의 줄에는 세 정수 $a_i$, $l_i$, $r_i$가 주어지며, $1 \le a_i \le 10^5$, $0 \le l_i \le r_i \le M$을 만족한다. $i$번째 용기에는 $a_i$ mg의 용액이 있고, 그 안의 YY 양은 $\frac{l_i}{M}a_i$ mg 이상 $\frac{r_i}{M}a_i$ mg 이하이다. 또한 $\sum_{i=1}^{n} a_i \ge s$이다.

달성 가능한 최대 오차의 최솟값을 출력하라. 이 값은 유리수임이 증명되어 있다. 기약분수 $p/q$ ($q > 0$)로 나타내고, $p$와 $q$를 공백으로 구분하여 한 줄에 출력하라.