Under construction

Still being built. Things may change

Knapsack Counting

Time limit1sMemory limit128 MB

Summary
Given up to 30 items with large weights and a capacity limit, count how many subsets have total weight at most the capacity.
Level

Medium7 of 10

Topics
Divide and conquer, Binary search, Sorting, Combinatorics
Solved
No attempts yet

Problem

You are given N items and one bag that can hold total weight at most C.

Each item may be chosen at most once, and choosing no items also counts as one way. Count how many subsets of the items have total weight at most C.

Input

The first line contains N and C. N is a positive integer no greater than 30, and C is a non-negative integer no greater than 10^9.

The second line contains the weights of the N items. Each weight is a positive integer no greater than 10^9.

Output

Print the number of ways to choose items whose total weight is at most C.

Examples6

  1. Example 1

    Input
    2 1
1 1
    Expected output
    3

  2. Example 2

    Input
    1 1
1
    Expected output
    2

  3. Example 3

    Input
    1 2
1
    Expected output
    2

  4. Example 4

    Input
    2 1
2 2
    Expected output
    1

  5. Example 5

    Input
    2 2
1 1
    Expected output
    4

  6. Example 6

    Input
    30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    Expected output
    1073741824