Vlejd chce bicykel, a ako správny hipster sa rozhodol, že si ho postaví sám. Základom bicykla je, samozrejme, trojuholníkový[^1] rám (na obrázku ružovou). Naň si Vlejd zohnal niekoľko starých kovových rúriek, z ktorých plánuje tri vybrať a pozvárať ich do tvaru trojuholníka. Následne chce rám natrieť hipsterskou ružovou farbou, ktorej má toľko, že ňou vie natrieť rúrky, ktoré sú spolu dlhé $$d$$ centimetrov.

Keďže by bola škoda po otvorení nepoužiť všetku ružovú farbu (zvyšok by zaschol a musel by sa vyhodiť), chce zistiť, či sa medzi jeho rúrkami nachádzajú tri také, ktoré tvoria trojuholník s obvodom presne $$d$$ centimetrov. (Ak také rúrky nemá, farbu si ušetrí na neskôr, vyberie iné rúrky a rámu uháčkuje slušivý obal z tyrkysovej priadze.) Pomôžete mu?

Úloha

Na vstupe dostanete obvod $$d$$, počet rúrok $$n$$ a dĺžky jednotlivých rúrok $$r_1, \dots, r_n$$.

Zistite, či sa z niektorých troch rúrok (môže sa stať, že viacero rúrok je rovnako dlhých, ale každú môžete použiť len raz) dá poskladať trojuholník s obvodom $$d$$.

Formát vstupu

Na prvom riadku vstupu je počet testovacích sád $$t$$.

Nasledujú dva riadky pre každú sadu (dokopy $$2t$$ riadkov). Na prvom riadku sú vždy dve celé čísla $$n$$ a $$d$$ ($$1 \leq d \leq 10^9$$) – počet rúrok a obvod trojuholníka. Na druhom riadku je $$n$$ celých čísel $$r_1, \dots, r_n$$ – dĺžky rúrok.

Pre jednotlivé vstupy platia nasledovné obmedzenia:

Formát výstupu

Pre každú testovaciu sadu vypíšte jeden riadok obsahujúci slová DA SA ak sa z rúrok na vstupe dá poskladať trojuholník s daným obvodom a NEDA SA inak.

Príklad

Input:

3
2 10
6 4
5 12
1 2 3 4 5
4 12
11 1 10 1

Output:

NEDA SA
DA SA
NEDA SA

V prvom prípade nemáme dosť rúrok na trojuholník; v druhom prípade môžeme postaviť trojuholník 3-4-5; v treťom prípade síce platí, že $$1+1+10 = 12$$, ale trojuholník z toho ani Vlejd nespraví.

1. Vlejd má rád trojuholníky. Viď príklad 6 z ostatnej série.↩