Greedy vs DP - Coin Change

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ distinct positive coin denominations including $1$ and a limit $V_{max}$, compare largest-coin-first greedy with the true minimum number of coins for every amount from $1$ through $V_{max}$. Find the smallest amount where greedy fails, or print -1 if none exists in the range.

Input

The first line contains $n,V_{max}$. The second line contains $n$ distinct denominations.

Output

If a counterexample exists, print the smallest $V$, the greedy count, and the optimal count. Otherwise print -1.

Subtasks

General constraints:

• $1 \le n \le 20$.

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

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

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

• Subtask 1 (20 points): $n \le 6$, $V_{max} \le 100$

• Subtask 2 (30 points): $n \le 12$, $V_{max} \le 2000$

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

Examples

Input

3 20
1 3 4

Output

6 3 2

Explanation

For amounts $1$ through $5$, greedy is still optimal. At $V=6$, greedy uses $4+1+1$ (three coins) while the optimum is $3+3$ (two coins), so $6$ is the smallest counterexample.