Tham lam và DP - Đổi tiền (Greedy vs DP - Coin Change)

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

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

Đề bài

Cho một hệ $n$ mệnh giá dương, phân biệt, có mệnh giá $1$, và giới hạn $V_{max}$. Với mỗi số tiền từ $1$ đến $V_{max}$, so sánh số xu của thuật toán lấy đồng lớn nhất trước với số xu tối ưu. Hãy tìm số tiền nhỏ nhất mà greedy thất bại. Nếu không có phản ví dụ trong đoạn, in -1.

Input

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

Output

Nếu có phản ví dụ, in một dòng gồm $V$, số xu greedy và số xu tối ưu cho $V$ nhỏ nhất. Nếu không có, in -1.

Subtask

Các giới hạn chung:

• $1 \le n \le 20$.

• $1 \le V_{max} \le 2\cdot10^4$.

• $1 \le c_i \le V_{max}$.

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

• Subtask 1 (20 điểm): $n \le 6$, $V_{max} \le 100$

• Subtask 2 (30 điểm): $n \le 12$, $V_{max} \le 2000$

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

Ví dụ

Input

3 20
1 3 4

Output

6 3 2

Giải thích

Từ $1$ đến $5$, greedy chưa tệ hơn tối ưu. Ở $V=6$, greedy dùng $4+1+1$ gồm $3$ xu, còn tối ưu dùng $3+3$ gồm $2$ xu. Đây là phản ví dụ nhỏ nhất.