Coin Change Counterexample

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ distinct positive coin denominations including $1$, and a target $V$, with unlimited supply of every coin. The greedy algorithm repeatedly takes the largest coin not exceeding the remaining amount. Compute the greedy coin count and the true optimal coin count, then report whether greedy fails on this instance.

Input

The first line contains $n,V$. The second line contains $n$ distinct denominations.

Output

Line 1 prints the greedy coin count. Line 2 prints the optimal coin count. Line 3 prints FAIL if greedy uses more coins than optimal, otherwise OK.

Subtasks

General constraints:

• $1 \le n \le 20$.

• $1 \le V \le 5000$.

• $1 \le c_i \le 5000$.

• The $c_i$ are distinct and one denomination equals $1$.

• Subtask 1 (20 points): $n \le 6$, $V \le 50$

• Subtask 2 (30 points): $n \le 12$, $V \le 500$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

3 6
1 3 4

Output

3
2
FAIL

Explanation

Greedy uses $4,1,1$, so it needs $3$ coins. The optimum is $3,3$, which uses $2$. Since $3>2$, the result is FAIL.