El Tira y Afloja es un deporte muy popular en la PSNIC. Las reglas son sencillas: dos equipos tiran de una cuerda en direcciones opuestas.

Se quiere llevar a cabo una competencia de tira y afloja en la PSNIC y muchos concursantes se han inscrito. Como árbitro, el trabajo de PSN0 es dividir a los concursantes en dos equipos, de modo que el juego pueda durar mucho tiempo. Dado que se han inscrito un total de ~2\cdot n~ concursantes, cada equipo estará formado por ~n~ concursantes. La cuerda tiene ~n~ puntos en el lado izquierdo y ~n~ puntos en el lado derecho.

Los concursantes inscritos son muy exigentes: cada uno tiene exactamente un punto en el lado izquierdo de la cuerda y un punto en el lado derecho que quiere usar.

Conociendo la fuerza de cada concursante, el organizador ahora le ha preguntado a PSN0 lo siguiente: dado un número entero ~k~, ¿es posible crear dos equipos, de modo que cada equipo tenga ~n~ concursantes, cada concursante use un lugar que quiera usar (por supuesto, no hay pueden haber dos concursantes que compartan el mismo lugar), y las sumas de las fortalezas de los dos equipos difieren como máximo en ~k~?

Subtareas

• Subtarea 1 (18 puntos): ~n \le 10~.
• Subtarea 2 (30 puntos): ~n \le 2000~.
• Subtarea 3 (23 puntos): ~n \le 30000~, ~s_i=1~.
• Subtarea 4 (29 puntos): ~n \le 30000~.

Entrada

La primera línea de la entrada contiene un entero positivo ~n~, el número de lugares en cada lado de la cuerda y un entero ~k\le 20n~, la máxima diferencia entre las fuerzas de los equipos. Los concursantes están numerados desde ~1~ hasta ~2n~.

Cada una de las siguientes ~2n~ líneas describen un concursante: la ~i~ésima de estas líneas contiene tres enteros positivos ~[l_i, r_i, s_i]~ (~1 \le l_i, r_i \le n~, ~1 \le s_i \le 20~), que especifica que el concursante ~i~ tiene una fuerza ~s_i~ y quiere usar el lugar ~l_i~ del lado izquierdo de la cuerda o el lugar ~r_i~ del lado derecho de la cuerda.

Salida

Imprime una línea que contenga YES o NO dependiendo de si es posible crear dos equipos que satisfacen los requerimientos dados.

Ejemplos

Entrada 1

4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

Salida 1

YES

Podemos asignar a los concursantes ~1~, ~3~, ~6~ y ~7~ al lado izquierdo (lo que resulta en un equipo de fuerza ~1 + 8 + 2 + 1 = 12~) y a los concursantes ~2~, ~4~, ~5~ y ~8~ al lado derecho. (lo que resulta en un equipo de fuerza ~2 + 2 + 5 + 2 = 11~). La diferencia de fortalezas entre equipos es ~1~.

Entrada 2

2 5
1 1 1
1 2 4
2 2 1
2 1 4

Salida 2

NO