Hay que limpiar \(S\) calles en a lo más \(K\) horas, y hay \(N\) limpiadores disponibles. El limpiador \(i\) limpia una calle en \(H_i\) horas y acepta un pago por calle de cualquier valor racional entre \(L_i\) y \(U_i\).

Se contrata un subconjunto \(C\) de limpiadores y a cada \(i \in C\) se le asigna una cantidad entera \(s_i \ge 1\) de calles y un pago por calle \(p_i\), de modo que:

• \(\sum_{i \in C} s_i = S\) (cada calle la limpia exactamente un limpiador);
• los limpiadores trabajan en paralelo y el trabajo termina en \(\max_{i \in C} s_i H_i\) horas, que debe ser como máximo \(K\);
• \(L_i \le p_i \le U_i\);
• el pago por hora \(p_i / H_i\) es el mismo para todos los contratados.

El pago total es \(\sum_{i \in C} s_i \, p_i\). Calcula el mínimo pago total posible, o indica que no hay forma de cumplir las condiciones. Las condiciones no aplican a quienes no se contratan.

Entrada

La primera línea tiene tres enteros \(N\), \(S\) y \(K\) \((1 \le N, S \le 10^5,\ 1 \le K \le 10^9)\).

Cada una de las siguientes \(N\) líneas describe a un limpiador con tres enteros \(H_i\), \(L_i\) y \(U_i\) \((1 \le H_i \le 10^5,\ 1 \le L_i \le U_i \le 100)\).

Salida

Si hay solución, una línea con dos enteros positivos \(x\) e \(y\) tales que \(x / y\) es la fracción irreducible del pago total mínimo. Si no hay solución, una línea con el carácter *.

Ejemplo 1

Entrada

2 15 10
1 4 10
2 2 8

Salida

80 1

Ejemplo 2

Entrada

2 7 9
3 4 10
2 2 8

Salida

68 3

Ejemplo 3

Entrada

2 15 10
1 4 10
5 2 8

Salida

*

Regional Latinoamericana 2025 del ICPC, problema C («Clean Streets»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.