Statement is not available in English language
E. Hazlos primos II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Andrés y Javi están jugando un juego en un pizarrón. Andrés escribe N números en el pizarrón y le dice a Javi que debe convertir los números escritos en números primos. Para darle emoción al juego, Andrés le dice a Javi que la forma en la que debe modificar los números debe ser la siguiente.

Javi puede elegir un número del pizarrón ai y realizar una de estas dos operaciones:

  • Dividir el número de forma entera entre 2 (ai = ⌊  ai  /  2 ⌋) con un costo de 1 punto
  • Sumarle o restarle 1 al número (ai = ai ± 1) con un costo de 1 punto.

Andrés le dice a Javi que tiene M puntos para gastar y con esta cantidad de puntos debe formar la mayor cantidad de números primos que pueda

Ayúdale a Javi a determinar la máxima cantidad de números primos que puede crear.

Input

La primera línea de la entrada tiene dos números N y M (1 ≤ N, M ≤ 1000) donde N es la cantidad de números que Andrés escribió en el pizarrón y M la cantidad de puntos que Javi puede gastar.

La segunda línea tiene N números ai (1 ≤ ai ≤ 1000) donde ai es el iésimo número que Andrés escribió en el pizarrón.

Output

Imprime una única línea, la cantidad de primos en el arreglo al final de aplicar las operaciones de forma óptima.

Subtareas

Los puntos de las subtareas son acumulables.

  • Subtarea 1 (37 puntos): Resuelve los casos de prueba que se muestran en los ejemplos.
  • Subtarea 2 (20 puntos): Resuelve el problema para 1 ≤ ai ≤ 23.
  • Subtarea 3 (40 puntos): Sin consideraciones adicionales.
Examples
Input
3 3
15 32 1
Output
3
Input
3 2
1 64 100
Output
2
Input
4 4
35 512 2 95
Output
4