5. O Vlejdovom bicykli

Vlejd chce bicykel, a ako správny hipster sa rozhodol, že si ho postaví sám. Základom bicykla je, samozrejme, trojuholníkový¹ 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í.