Programacion Competitiva Bolivia

Mi musica Favorita

Tendras que hacer un viaje muy largo a otra ciudad, asi que una muy buena compañía será tu musica favorita. Tu auto cuenta con una lector de casetes, pero existe un pequeno inconveniente ya que tu musica favorita se encuentra en CD's. Asi que es necesario grabar tu musica del CD al casete

Tu tienes N minutos disponibles en el casete (Ya que existe el limite de la cinta de casete). Asi que el objetivo del problema es llenar el maximo numero de minutos posibles en la cinta del casete.

N es un entero (1≤N≤1500) T es un entero (1≤T≤20) Ningun Ti sera mas grande que N

Input

La entrada consiste en un entero N (minutos que soporta la cinta del casete), seguidamente por un entero T (Numero de pistas que tiene el CD) seguidamente por T enteros que representa el tiempo de duracion de cada pista.

Output

Imprimir las pistas (la duracion de cada pista) que maximizan el uso de la cinta del casete.

Example

Input:
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

Output:
1 4
8 2
10 5 4
10 23 1 2 3 4 5 7
4 10 12 9 8 2