Prizes

Interview

Time limit1sMemory limit1024 MB

Summary

Given N prize prices and a budget K, determine whether three different prizes have prices that sum to exactly K.

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

Problem

Kevin is tasked with buying prizes for the top three finishers of the olympiad final. His budget is $K$ euros. He has a list of the prices of $N$ possible prizes. Help Kevin determine whether he can buy 3 different prizes so that the budget is spent exactly.

Input

The first line contains two integers $N$ ( $3 \le N \le 10^4$ ) and $K$ ( $1 \le K \le 3 \cdot 10^8$ ), the number of possible prizes and the budget. The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ( $0 \le A_i \le 10^8$ ), the prices of the prizes. Some prizes are free.

Output

Print JAH if three different prizes can be chosen so that their total price is exactly $K$ . Otherwise, print EI.

Examples2

Example 1
Input
```
4 8
2 1 5 3
```
Expected output
```
JAH
```
Example 2
Input
```
3 9
1 2 3
```
Expected output
```
EI
```