The Knapsack Problem

Problem Background

Special for beginners, ^_^

Problem Description

A simple knapsack problem. There is a knapsack with a maximum load capacity of $s\;(1\le s \le 100)$. There are $n\;(1\le n \le 10)$ items whose weights are $w_1,w_2,\dots,w_n\;(1 \le i \le n)$, all positive integers. Choose some of the $n$ items so that the sum of their weights is exactly $s$. Finding any one valid solution is enough.

Input Format

The first line contains the total number of items and the capacity of the knapsack. The second line contains the weight of each item.

Output Format

For each selected item, output its index and its weight, one item per line.

If there is no solution, output not found (the output does not include the quotation marks).

Sample Input

5 10
1 2 3 4 5

Sample Output

1 1
2 2
3 3
4 4

Constraints

1s, 1024KiB for each test case.