Diamantes P75018

Un príncipe muy rico tiene exactamente n diamantes. Cada diamante 1≤ i≤ n tiene un cierto valor v_i. La tradición manda que, antes de casarse, el príncipe haga un regalo de valor exactamente V a su princesa. El príncipe quiere regalarle exactamente dos de sus diamantes, pero no sabe como decidir rápidamente si puede hacerlo o no. ‘?Puedes ayudar a este pringado?

Por ejemplo, si n=6 y el valor de los diamantes es 5, 8, 6, 2, 6, 20, entonces es posible hacer un regalo de valor V=10 (8+2) o bien un regalo de valor V=12 (6+6), pero no es posible hacer un regalo de valor V=9.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con el valor V del regalo (un natural entre 1 y 10⁸) y el número n de diamantes (un natural entre 1 y 10⁵) en este orden. Después vienen n naturales entre 1 y 10⁸ indicando el valor de cada diamante. Un caso con V = n = 0 marca el final de la entrada.

Salida

Para cada caso, escribid en una línea “married” o bien “single” según si el príncipe puede hacer el regalo o no.