Exact budget baskets

Problem

A store has n products with positive prices. A basket is any group of products, and two products with the same price at different positions are different products. Count the baskets whose total price is exactly the target.

Input, output and limits

Input: Line 1: n and the target T. Line 2: n prices.
Output: One integer: the number of baskets.
Constraints: 1 ≤ n ≤ 15
1 ≤ price ≤ 50
1 ≤ T ≤ 200

Examples

Example

Input

4 7
2 3 4 5

Output

Baskets {2, 5} and {3, 4}.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Sort the prices. Choose products from left to right using a start index.

Hint 2

When a price is larger than what is left, stop the loop: every later price is larger too.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All orders of tasksmedium
Make change with reusemedium
Keypad wordseasy
Balanced bracket stringsmedium
Courier routeseasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Backtracking problems

Problem

Input, output and limits

Examples

Hints

More Backtracking problems