Con el fin de mejorar la conexión en el IPVCE, Alfredo ha conseguido una varilla de metal larga para hacer una antena. Sin embargo, la varilla está rota en ~n~ ~(1\le n\le 10^6)~ trozos de longitud ~a_i~ ~(1\le a_i\le 10^9)~, por lo que Alfredo decidió pedirle ayuda a Valido para cortarla de tal forma que cada trozo tuviera la misma longitud y así poder distribuir varias antenas por la escuela.

Este por supuesto decidió dejar que los concursantes de informática fueran los que cortaran la varilla, no sin antes advertirles que la varilla tenía que estar lista para el concurso provincial, así que tenían que cumplir la tarea realizando la menor cantidad de cortes posible.

Al final del día Alfredo o Valido harán una pregunta para asegurarse de que cumplieron la tarea correctamente. Alfredo preguntará por el tamaño en el que quedaron los trozos de la varilla, y Valido preguntará cuántos cortes le realizaron. Una respuesta incorrecta terminará con la realización del concurso provincial sin usar DMOJ.

Puntaje

La calificación se divide en dos grupos:

Grupo 1: ~p=0~ (50 puntos).

Grupo 2: ~p=1~ (50 puntos).

Entrada

La primera línea contiene dos enteros separados por espacio ~n~ ~(1\le n\le 10^6)~ y ~p~ ~(p\in \{0,1\})~. La cantidad de trozos en los que está rota la varilla y el identificador de la persona que hizo la pregunta, respectivamente.

La segunda línea contiene ~n~ enteros ~a_i~ ~(1\le a_i\le 10^9)~ que representan la longitud del ~i~-ésimo trozo de la varilla.

Salida

Un entero representando la respuesta a la pregunta de Alfredo si ~p=0~, o a la pregunta de Valido si ~p=1~.

Ejemplo de Entrada #1

4 0
6 4 6 10

Ejemplo de Salida #1

2

Ejemplo de Entrada #2

4 1
6 4 6 10

Ejmplo de Salida #2

9

La siguiente figura corresponde a la varilla de los casos de ejemplo después de ser cortada.

(Imagen por Adrian Pacheco Rubio)

Los pequeños segmentos tienen longitud ~2~ (sin contar las antenas de la varilla), y la cantidad de divisiones que se realizó fueron ~9~ (se puede demostrar que esta es la menor cantidad de cortes necesarios para dividir la varilla en segmentos iguales).