La carrera hacia la Casa Blanca
A Donald se le ha metido en la cabeza ser presidente de Estados Unidos. Ha mirado las normas y las cumple: es ciudadano del país por nacimiento, tiene al menos 35 años (¡la primera vez que le pintaron fue en 1934!) y lleva siendo residente al menos 14 años. Así que ha elegido un partido político y se ha puesto a analizar sus posibilidades.
Las reglas son bastante conocidas. El candidato del partido es elegido en la convención nacional que tiene lugar el verano del año electoral. En esa convención, los delegados que vienen de los distintos estados votan entre los distintos aspirantes; el que tenga más votos se convierte en el candidato del partido.
Los delegados, eso sí, se rigen por unas normas claras: los K delegados de un estado concreto apoyarán al mismo candidato, aquel que resultó ganador en las votaciones primarias que se hicieron en su estado durante los primeros meses del año y en el que pueden votar todos los afiliados al partido.
El objetivo de Donald ahora está en las primarias de cada estado; tiene que hacer una buena campaña para garantizar que en la convención nacional terminará ganando al otro aspirante del partido.
En su análisis de la situación ha visto que en cada estado hay tres tipos de personas: aquellas que le votarán, aquellas que no le votarán y un grupo que aún está indeciso. Evidentemente la campaña de Donald debe centrarse en esos indecisos. ¿A cuántos debe convencer como mínimo para garantizarse que será el próximo candidato a la Casa Blanca?
Ten en cuenta que al ser un pato, en caso de empate siempre sale perdiendo. Si en un estado hay empate, los delegados votarán al otro candidato. Y si en la votación de la convención nacional hay empate a votos, también perderá la carrera hacia la Casa Blanca.
Entrada
La entrada estará compuesta por distintos casos de prueba.
Cada caso comienza con una línea indicando el número N de estados del país (1 ≤ N ≤ 100). A continuación vendrán N líneas describiendo cada estado con cuatro números: número de delegados que aporta (al menos uno), cantidad de gente que sabemos que votará a Donald, cantidad de gente que votará al otro aspirante y, por último, número de indecisos.
El número total de delegados que van a la convención nacional no supera los 5.000, y el número de votantes por estado nunca será mayor de diez millones.
Salida
Por cada caso de prueba se escribirá una única línea indicando a cuántos indecisos debe convencer como mínimo Donald para asegurarse ser el candidato a la presidencia. Si los datos reflejan que no podrá ser el candidato por mucho que invierta, se escribirá IMPOSIBLE.
Entrada de ejemplo
3 8 1000 500 0 8 500 1000 0 1 100 100 25 1 8 500 1000 500 1 8 0 0 100
Salida de ejemplo
13 IMPOSIBLE 51