Benito es un amante de la aventura y la ciencia. Un día mientras caminaba en el reino de Elfrieden intentando encontrar una ruta más corta hacia la biblioteca descubrío una cueva repleta de cristales mágicos.
Ahí conoció a un mago-investigadora llamada Ichi que le hablo sobre estos. Ichi explico que ha estado estudiando estos cristales por mucho tiempo y ha descubierto que tienen distintos poderes y fortalezas. Por lo que las clasifico en lo que el llamo familias. Cada familia tiene un color único y con distinto poder, el lo llamo chispa mágica. Como el nombre de los cristales estan escrito en un alfabeto distinto, Ichi se dio a la tarea de convertir el alfabeto inglés por simplicidad, pero nota que tiene una diferencia ya que su alfabeto tiene mas letras por lo que después de la traducción las mayúsculas y minúsculas tienen un significado distinto. Además de que este no utiliza los números para los nombres.
Ichi te comentó que quiere hacer más experimentos pero debido a sus responsabilidades no tiene mucho tiempo libre. El quiere probar una teoría sobre la resistencia y poder de los cristales. Por lo que quiere tu ayuda para realizar un experimento muy particular. Te da la tarea de que lo ayudes a escoger cristales para el experimento. Pero hay una regla importante que debes seguir: Solo elegir un cristal de cada familia, es decir, no puedes elegir dos cristales del mismo color.
La meta es elegir K cristales que cuando se unan nos den el poder más grande posible.
Benito ha hecho un reporte con todos los cristales que existen en la cueva. Pero esto lo dejó sin energía. Por eso te pide que lo ayudes a encontrar los cristales que necesita.
La primer línea contiene dos números N y K. Estos representan el total de cristales mágicos que existen en la cueva (3 ≤ N ≤ 106) y el número de cristales que Ichi necesita para su experimento (1 ≤ K ≤ N) respectivamente.
La siguiente línea contiene dos valores Ci y Pi. Ci es una cadena (1 ≤ |Ci| ≤ 1000) que representa el nombre de la familia y Pi un entero (1 ≤ Pi ≤ 109) que representa el poder de dicho cristal.
Por cada caso se deberán imprimir lo siguiente: En la primer línea el poder que tienen todos los cristales seleccionados unidos. En caso que no sea posible elegir cristales que cumplan las restricciones, imprimir la palabra "IMPOSIBLE". Si existe una solución, entonces en la segunda línea, una lista con los indices ordenados de los cristales que fueron seleccionados. Si existen multiples soluciones, entonces imprimir la que sea lexicrográficamente menor.
5 3ROJO 5AZUL 3ROJO 4VERDE 6AZUL 2
14 1 2 4
4 3AMARILLO 4GRIS 5AMARILLO 6GRIS 7
IMPOSIBLE
En el caso dos, solo hay 2 colores distintos por lo que la salida es "IMPOSIBLE"