Burrito King

Albert and Barney went to "Burrito King", a restaurant that opened yesterday. Albert received an opening gift card, so the two friends can get one burrito for free. The amount of each ingredient is capped: the burrito holds at most $g_i$ grams of ingredient $i$.

Every ingredient has two satisfaction values. $a_i$ is the joy that one gram of ingredient $i$ gives Albert, and $b_i$ is the unhappiness that the same gram gives Barney. If the burrito holds $s_i$ grams of ingredient $i$, Albert's total joy is

$\sum_{i=1}^{n} s_i a_i$

and Barney's total unhappiness is

$\sum_{i=1}^{n} s_i b_i$

Here $s_i$ is not necessarily an integer, and $0 \le s_i \le g_i$.

Albert wants his total joy to be at least $A$. Barney is his best friend, so Albert wants Barney's total unhappiness to be at most $B$. Among the burritos that meet both conditions, Albert picks one with the largest total joy.

Choose the amounts $s_i$ that meet both conditions, or find out that no such burrito exists.

The first line contains the number of ingredients $n$, the joy Albert asks for at least, $A$, and the unhappiness Barney is allowed at most, $B$ ($1 \le n \le 100\,000$, $0 \le A, B \le 10^9$).

Each of the next $n$ lines describes one ingredient with the maximal number of grams $g_i$, the joy per gram $a_i$, and the unhappiness per gram $b_i$ ($0 \le g_i, a_i, b_i \le 100$).

If no burrito meets both conditions, print -1 -1 on the first line.

Otherwise print two lines. The first line holds the maximal joy and the unhappiness that comes with it. The second line holds the amounts $s_1, \dots, s_n$ of ingredients 1 through $n$, separated by single spaces.

Print every number as an exact reduced fraction. Print an integer value as p with no denominator, and any other value as p/q ($q \ge 2$, $\gcd(p, q) = 1$).

Several burritos can reach the maximal joy, so this rule fixes one answer.

1. Every ingredient with $a_i = 0$ or $g_i = 0$ gets $s_i = 0$.
2. Every remaining ingredient with $b_i = 0$ gets $s_i = g_i$.
3. Sort the other ingredients by $a_i / b_i$ in decreasing order, breaking a tie by the smaller index, and walk that order. If the unused part of the unhappiness budget pays for all $g_i$ grams, use $g_i$ grams. Otherwise use only the amount the unused part pays for, and leave every later ingredient at $0$ grams.

This rule reaches the maximal joy, and among the burritos that reach it the one with the smallest unhappiness.