Un día, después de una ardua competencia de programación competitiva, $N$ participantes decidieron ir a comer algo porque llevaban más de 10 horas sin comer. Para celebrar lo bien que les fue en la competencia, fueron a un lugar inédito de hamburguesas (eso dicen dos de nuestros participantes, Waldo y Luis), donde hay exactamente $M$ tipos distintos de hamburguesas.

Cada competidor, con mucha hambre, puede recibir varias hamburguesas, pero ningún competidor puede recibir dos hamburguesas del mismo tipo.

Tu tarea es determinar el mínimo número de hamburguesas que hay que repartir para garantizar que al menos un tipo de hamburguesa sea recibido por al menos $K$ competidores.

T número de casos de prueba 

Para cada caso: tres enteros:

  • N número de participantes

  • M número de tipos de hamburguesas

  • K número de participantes que deben compartir un tipo de hamburguesa

Para cada caso, imprime el mínimo número de hamburguesas que hay que repartir para garantizar la condición.

Primer caso

1. Cada tipo de hamburguesa puede repartirse como máximo 2 veces sin que 3 personas lo tengan (porque queremos evitar compartir un tipo entre 3 personas).
2. Si repartimos 10 hamburguesas:
   • Podríamos dar 2 hamburguesas de cada tipo: \(5 \text{ tipos} \times 2 \text{ hamburguesas} = 10\) hamburguesas.
   • En este escenario, ningún tipo tiene 3 participantes, aún no se cumple la meta.
3. Si repartimos 11 hamburguesas:
   • Tenemos 5 tipos, pero con 11 hamburguesas al menos un tipo debe recibir 3 hamburguesas.
   • Entonces, al menos un tipo será recibido por 3 participantes, cumpliendo la meta.

Resultado: 11 hamburguesas mínimas.

Segundo caso

1. Cada tipo de hamburguesa puede repartirse 1 vez sin que 2 personas lo tengan.
2. Si repartimos 4 hamburguesas:
   • Podríamos dar 1 hamburguesa de cada tipo: \(4 \text{ tipos} \times 1 \text{ hamburguesa} = 4\) hamburguesas.
   • En este escenario, ningún tipo está compartido, aún no se cumple la meta.
3. Si repartimos 5 hamburguesas:
   • Tenemos 4 tipos, pero con 5 hamburguesas al menos un tipo será recibido por 2 participantes.
   • Esto asegura que la condición de compartir al menos un tipo entre 2 participantes se cumpla.

Resultado: 5 hamburguesas mínimas.