题目背景

译自 ICPC 2024 Yokohama Regional Contest。

题目描述

我们来准备一个使用化学物质横滨黄（Yokohama Yellow），简称 YY 的实验。你有一些装有 YY 水溶液的容器。虽然 YY 在每种溶液中都均匀溶解，但不同容器中的浓度可能不同。你将从一些容器中取出任意量的溶液，并将它们混合以制备具有预定总量的新溶液。

理想情况下，混合溶液应包含目标量的 YY，但存在一个问题。虽然每个容器中溶液的确切量是已知的，但每种溶液中 YY 的量只保证落在某个范围内。由于这种不确定性，很难使混合溶液中 YY 的量与目标量精确匹配。尽管如此，你可以确保误差（与目标量的差值）永远不会超过某个限制。

更精确地说，设混合溶液中 YY 的目标量和实际量分别为 $y_t$ 毫克和 $y_a$ 毫克。给定从容器中取出的溶液量，$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$ 表示 YY 溶液容器的数量。混合溶液的预定总量为 $s$ 毫克，YY 的目标量为 $\frac{c}{M} s$ 毫克。接下来的 $n$ 行中的第 $i$ 行包含三个整数 $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$ 毫克溶液，并且其中 YY 的量保证在 $\frac{l_i}{M} a_i$ 毫克和 $\frac{r_i}{M} a_i$ 毫克之间（包括两端）。它们满足 $\sum_{i=1}^n a_i \ge s$。

输出格式

最大误差的最小值可以被证明是一个有理数。将该值表示为不可约分数 $p/q$，其中 $q > 0$，输出一行两个整数 $p,q$，以空格分隔。

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

1 2

2 10 5000
7 4500 5500
12 3500 6000

4 5

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

0 1

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

23901191037 67820000