teddy online judge

39. Casino

Limite de tiempo : 1 seg.   Total runs : 132  Aceptados : 27

En un casino pusieron unas nuevas máquinas tragamonedas. En estas máquinas hay tres números G, S y M. G indica cuantas monedas ganó la última persona que jugó mientras que S y M sirven para decidir cuantas monedas se le darán al siguiente jugador. Cada vez que alguien deposita una moneda puede decidir que ganancia quiere tener, puede quedarse con G+S mod M, o bien, quedarse con G*S mod M. Una vez que se toma la decisión, la máquina le da al jugador su ganancia y se coloca un nuevo valor de S en la pantalla. Las siguientes líneas son un ejemplo de una secuencia de juegos en los que M=5 y el número total de monedas ganadas es 11:

Nota: “X mod M” indica el residuo al hacer la división X/M, por ejemplo:

15 mod 8 = 7
10 mod 2 = 0
3 mod 10 = 3

Después de jugar un rato en la máquina te preguntas ¿Cuál será la mayor cantidad de monedas que me puedo llevar si conociera los valores de S que me van a salir en los siguientes juegos y supiera que G=0 al principio?

Problema

Hacer un programa que lea la secuencia de los valores de S y escriba cual es la mayor cantidad de monedas que puedes obtener.

Entrada

Para cada caso de prueba debes leer primero dos enteros, el primero de ellos es M (2 ≤ M ≤ 100) y el segundo es K (1 ≤ K ≤ 100) que indica el tamaño de la secuencia. A continuación tienes que leer la secuencia de los valores de S (0 ≤ S < M).

Salida

Para cada caso de prueba debes escribir una línea de texto con el mensaje “Al final me puedo quedar con T monedas.”, siendo T la mayor cantidad de monedas que te puedes llevar.

Sample Input/Output

Input

3
5 3 3 3 1
4 4 2 2 0 0
10 1 9

Output

Al final me puedo quedar con 11 monedas.
Al final me puedo quedar con 6 monedas.
Al final me puedo quedar con 9 monedas.