J. Mixing Solutions
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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_{\mathrm{t}}$$$ mg (milligrams) and $$$y_{\mathrm{a}}$$$ mg, respectively. Given the amounts of solution taken from the containers, $$$y_{\mathrm{a}}$$$ is guaranteed to fall within a certain range. The maximum error is defined as the maximum of $$$|y_{\mathrm{a}} - y_{\mathrm{t}}|$$$ when $$$y_{\mathrm{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.

Input

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 \leq n \leq 1000$$$, $$$1 \leq s \leq 10^5$$$, and $$$0 \leq c \leq 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 \leq a_i \leq 10^5$$$ and $$$0 \leq l_i \leq r_i \leq M$$$. These integers indicate that the $$$i$$$-th container has $$$a_i$$$ 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_{i=1}^n a_i \geq s$$$.

Output

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 \gt 0$$$, and output $$$p$$$ and $$$q$$$ separated by a space on a single line.

Examples
Input
3 10 5000
10 2000 3000
10 4000 6000
10 7000 8000
Output
1 2
Input
2 10 5000
7 4500 5500
12 3500 6000
Output
4 5
Input
3 1 4159
1 1 1
1 100 100
1 10000 10000
Output
0 1
Input
6 12345 6789
2718 2818 2845
9045 2353 6028
7471 3526 6249
7757 2470 9369
9959 5749 6696
7627 7240 7663
Output
23901191037 67820000