Taro's Shopping

Time limit2sMemory limit512 MB

Summary

Given item prices and a budget, find the largest sum of two distinct items that does not exceed the budget.

Level: Medium4 of 10
Topics: Two pointers, Sorting, Array
Solved: No attempts yet

Problem

Mammy decided to give Taro his first shopping experience. She tells him to pick any two items he likes from the shopping catalogue, but Taro cannot settle on two, because every item looks attractive. So he plans to buy the pair of items whose price sum is as large as possible without going over the amount Mammy allows. Buying two copies of the same item is boring, so he picks two different items.

Help Taro choose the two items. The price list of all the items is given. Among all pairs of two items in the list, find the pair whose price sum is the largest one that does not exceed the allowed amount, and report that sum. Taro buys exactly two items, not one, and not three or more. Two or more items in the list may be priced equally.

Input

The input consists of several datasets, each in the following format.

n m
a1 a2 ... an

One dataset takes two lines. The first line holds the number of items $n$ and the maximum payment allowed $m$ . $n$ is an integer with 2 ≤ $n$ ≤ 1,000, and $m$ is an integer with 2 ≤ $m$ ≤ 2,000,000. The second line holds the prices of the $n$ items. $a_i$ (1 ≤ $i$ ≤ $n$ ) is the price of the $i$ -th item, an integer between 1 and 1,000,000 inclusive.

The end of the input is marked by a line containing two zeros. The sum of $n$ over all datasets does not exceed 50,000.

Output

For each dataset, print on one line the largest price sum of a pair of items that does not exceed the allowed amount $m$ . If the price sum of every pair exceeds $m$ , print NONE instead of that value.

Examples5

Example 1

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

Expected output

40
10
99
NONE
20

Example 2
Input
```
2 2
1 1
2 2
1 2
0 0
```
Expected output
```
2
NONE
```

Example 3

Input

2 2000000
1000000 1000000
2 1999999
1000000 1000000
0 0

Expected output

2000000
NONE

Example 4

Input

5 20
10 10 10 10 10
5 19
10 10 10 10 10
0 0

Expected output

20
NONE

Example 5

Input

6 15
1 3 7 8 12 14
6 13
14 12 8 7 3 1
6 2
1 1 1 1 1 1
0 0

Expected output

15
13
2