P12787 [ICPC 2024 Yokohama R] Mixing Solutions

译自 [ICPC 2024 Yokohama Regional Contest](https://icpc.jp/2024/)。

我们来准备一个使用化学物质横滨黄（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$，以空格分隔。