Phản ví dụ đổi tiền tham lam (Coin Change Counterexample)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $n$ mệnh giá đồng xu dương, phân biệt và luôn có mệnh giá $1$, cùng số tiền $V$. Có vô hạn xu mỗi loại. Thuật toán tham lam được định nghĩa là luôn lấy đồng lớn nhất không vượt phần tiền còn lại. Hãy tính số xu mà thuật toán tham lam dùng và số xu tối ưu thật sự. Sau đó kết luận tham lam có thất bại trên dữ liệu này hay không.

Input

Dòng đầu chứa $n,V$. Dòng thứ hai chứa $n$ mệnh giá phân biệt.

Output

Dòng 1 in số xu của tham lam. Dòng 2 in số xu tối ưu. Dòng 3 in FAIL nếu tham lam dùng nhiều xu hơn tối ưu, ngược lại in OK.

Subtask

Các giới hạn chung:

• $1 \le n \le 20$.

• $1 \le V \le 5000$.

• $1 \le c_i \le 5000$.

• Các $c_i$ phân biệt và có một $c_i=1$.

• Subtask 1 (20 điểm): $n \le 6$, $V \le 50$

• Subtask 2 (30 điểm): $n \le 12$, $V \le 500$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

3 6
1 3 4

Output

3
2
FAIL

Giải thích

Tham lam lấy $4,1,1$ nên dùng $3$ xu. Tối ưu lấy $3,3$ nên chỉ dùng $2$ xu. Vì $3>2$, kết luận FAIL.