부리토 킹

앨버트와 바니는 어제 문을 연 식당 "부리토 킹"에 갔다. 앨버트가 개점 기념 상품권을 받아서 두 사람은 부리토 하나를 공짜로 받을 수 있다. 대신 재료 사용량에 제한이 있다. $i$번 재료는 최대 $g_i$그램까지만 넣을 수 있다.

재료마다 만족도 수치가 두 개 붙는다. $a_i$는 $i$번 재료 1그램이 앨버트에게 주는 기쁨이고, $b_i$는 같은 1그램이 바니에게 주는 불만이다. 부리토에 $i$번 재료를 $s_i$그램 넣었을 때 앨버트의 기쁨 총합은

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

이고, 바니의 불만 총합은

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

이다. $s_i$는 정수가 아니어도 되며 $0 \le s_i \le g_i$를 만족한다.

앨버트는 자기 기쁨 총합이 $A$ 이상이기를 바란다. 바니는 가장 친한 친구라서 바니의 불만 총합은 $B$ 이하로 누르고 싶다. 두 조건을 모두 만족하는 부리토 중에서 앨버트는 기쁨이 가장 큰 것을 고른다.

두 조건을 만족하는 재료의 양 $s_i$를 정하거나, 그런 부리토가 없음을 알아내자.

첫째 줄에 재료의 개수 $n$, 앨버트가 원하는 기쁨의 하한 $A$, 바니의 불만 상한 $B$가 주어진다 ($1 \le n \le 100\,000$, $0 \le A, B \le 10^9$).

다음 $n$개 줄에 재료 정보가 한 줄에 하나씩, $i$번 재료의 최대 사용량 $g_i$, 1그램당 기쁨 $a_i$, 1그램당 불만 $b_i$ 순서로 주어진다 ($0 \le g_i, a_i, b_i \le 100$).

두 조건을 동시에 만족하는 부리토가 없으면 첫째 줄에 -1 -1을 출력한다.

그렇지 않으면 두 줄을 출력한다. 첫째 줄에는 달성할 수 있는 최대 기쁨과 그때의 불만을, 둘째 줄에는 1번부터 $n$번까지 재료의 사용량 $s_1, \dots, s_n$을 공백 하나로 구분해 출력한다.

모든 수는 기약분수로 정확히 출력한다. 값이 정수면 분모를 붙이지 않고 p로, 정수가 아니면 p/q 꼴로 출력한다 ($q \ge 2$, $\gcd(p, q) = 1$).

기쁨이 최대인 부리토가 여러 개일 수 있으므로 다음 규칙으로 답을 하나로 정한다.

1. $a_i = 0$이거나 $g_i = 0$인 재료는 $s_i = 0$이다.
2. 남은 재료 중 $b_i = 0$인 재료는 $s_i = g_i$이다.
3. 나머지 재료는 $a_i / b_i$가 큰 순서로, 값이 같으면 번호가 작은 순서로 본다. 이 순서대로, 남은 불만 예산이 $g_i$그램 값을 전부 감당하면 그 재료를 $g_i$그램 쓰고, 감당하지 못하면 남은 예산으로 살 수 있는 양만 쓰고 그 뒤의 재료는 모두 $0$그램으로 둔다.

이 규칙은 기쁨을 최대로 만들며, 그 최대를 달성하는 불만 중 가장 작은 값을 준다.