Taro's Shopping

時間制限 : 8 sec, メモリ制限 : 262144 KB
英語版はこちら

太郎君の買物

お母さんは太郎に初めてのお買物経験をさせてみることにした. お母さんは商品カタログから好きなものを二つ選んでいいのよと言うのだが,欲しいものばかりなので太郎は決められなくて困った. そこで,お母さんが許してくれる金額の範囲で, 合わせた値段が一番高くなる二つの品物を買うことにした. 同じものが二つあってもつまらないから,別々の二つが欲しい.

太郎が二つの品物を選ぶのを助けてほしい. 全商品の価格表が与えられる. この中の品物二つの組のうち,価格の合計が許容額の範囲で最も高いものを見つけ,その価格の合計を答えよ. 太郎が買う品物の数は二つに決まっていて,一つでも,三つ以上でもいけない. 二つ以上の品物が同じ価格のこともあることに注意せよ.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

n m
a1 a2an

データセットは 2 行からなる. 1 行目には品物の個数 n と使ってよい最大の金額 m が与えられる. n は整数であり,2 ≤ n ≤ 1000 が成り立つ. m は整数であり,2 ≤ m ≤ 2,000,000 が成り立つ. 2 行目には n 個の品物の価格が与えられる. ai (1 ≤ in) が i 番目の品物の価格である. この値は整数であり,1 以上 1,000,000 以下である.

入力の終わりは,2 個のゼロだけからなる行で表される. 全データセットの n の合計は 50,000 を超えない.

Output

各データセットについて,品物二つの組のうち価格の合計が許容額 m を超えない範囲で最も高いものを見つけ,その価格の合計を 1 行に出力せよ. どの品物の組も価格合計が m を超える場合は,代わりに NONE と出力すること.

Sample Input

3 45
10 20 30
6 10
1 2 5 8 9 11
7 100
11 34 83 47 59 29 70
4 100
80 70 60 50
4 20
10 5 10 16
0 0

Output for the Sample Input

40
10
99
NONE
20

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tsukuba, Japan, 2017-07-14
http://icpc.iisf.or.jp/2017-tsukuba/