시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB125436.364%

문제

Let’s prepare for an experiment with the chemical Yokohama Yellow, or YY in short. You have several containers of aqueous solution of YY. While YY is evenly dissolved in each solution, the concentration may differ among containers. You will take arbitrary amounts of solution from some of the containers and mix them to prepare a new solution with the predetermined total amount.

Ideally, the mixed solution should contain the target amount of YY, but there is a problem. While the exact amount of solution in each container is known, the amount of YY in each solution is guaranteed only to fall within a certain range. Due to this uncertainty, it is difficult to match the amount of YY in the mixed solution exactly to the target amount. Still, you can ensure that the error, the difference from the target amount, will never exceed a certain limit.

To be more precise, let the target and actual amounts of YY in the mixed solution be $y_t$ mg (milligrams) and $y_a$ mg, respectively. Given the amounts of solution taken from the containers, $y_a$ is guaranteed to fall within a certain range. The maximum error is defined as the maximum of $|y_a - y_t|$ when $y_a$ varies within this range.

Find the minimum achievable value of the maximum error, given that you can take any portion of the solution in each container as long as their total is equal to the predetermined amount.

입력

The input consists of a single test case of the following format.

$n$ $s$ $c$

$a_1$ $l_1$ $r_1$

$\vdots$

$a_n$ $l_n$ $r_n$

The first line contains three integers, $n$, $s$, and $c$, satisfying $1 ≤ n ≤ 1000$, $1 ≤ s ≤ 10^5$, and $0 ≤ c ≤ M$, where $M = 10^4$ here and in what follows. Here, $n$ denotes the number of containers of YY solution. The predetermined total amount of the mixed solution is $s$ mg, and the target amount of YY is $\frac{c}{M}s$ mg. The $i$-th of the following $n$ lines contains three integers, $a_i$, $l_i$, and $r_i$, satisfying $1 ≤ a_i ≤ 10^5$ and $0 ≤ l_i ≤ r_i ≤ M$. These integers indicate that the $i$-th container has ai mg of solution and that the amount of YY in it is guaranteed to be between $\frac{l_i}{M}a_i$ mg and $\frac{r_i}{M} a_i$ mg, inclusive. They satisfy $\sum^{n}_{i=1} {a_i} ≥ s$.

출력

The minimum achievable value of the maximum error can be proven to be a rational number. Express the value as an irreducible fraction $p/q$ with $q > 0$, and output $p$ and $q$ separated by a space on a single line.

예제 입력 1

3 10 5000
10 2000 3000
10 4000 6000
10 7000 8000

예제 출력 1

1 2

예제 입력 2

2 10 5000
7 4500 5500
12 3500 6000

예제 출력 2

4 5

예제 입력 3

3 1 4159
1 1 1
1 100 100
1 10000 10000

예제 출력 3

0 1

예제 입력 4

6 12345 6789
2718 2818 2845
9045 2353 6028
7471 3526 6249
7757 2470 9369
9959 5749 6696
7627 7240 7663

예제 출력 4

23901191037 67820000