using namespace std;
using vi = vector<int>;
using ll = long long;
const int MOD = 1e9 + 7;
int solve(int x, const vi &c)
{
    vi dp(x + 1, 0);
    dp[0] = 1;
    for (int s = 1; s <= x; ++s)
    {
        for (auto ci : c)
        {
            if (s - ci < 0)
                break;
            dp[s] = (dp[s] + dp[s - ci]) % MOD;
        }
    }
    return dp[x];
}
int main(void)
{
    int n, x;
    cin >> n >> x;
    vi c(n);
    for (auto &ci : c)
        cin >> ci;
    sort(c.begin(), c.end());
    cout << solve(x, c) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int NMAX = 1e2 + 11;
const int INF = 1e9;
int n, x, c[NMAX];
int solve(void)
{
    vvi dp(n + 1, vi(x + 1, INF));
    for (int i = 1; i <= n; ++i)
        dp[i][0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= x; ++s)
        {
            int &ans = dp[i][s];
            ans = dp[i - 1][s];
            if (s - c[i - 1] >= 0)
                ans = min(ans, dp[i][s - c[i - 1]] + 1);
        }
    }
    return (dp[n][x] == INF ? -1 : dp[n][x]);
}
int main(void)
{
    cin >> n >> x;
    for (int i = 0; i < n; ++i)
        cin >> c[i];
    cout << solve() << endl;
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 1e6 + 11;
const int MOD = 1e9 + 7;
int mem[NMAX];
bool vis[NMAX];
ll dp(int sum)
{
    if (sum < 0)
        return 0;
    else if (sum == 0)
        return 1;
    int &ans = mem[sum];
    if (vis[sum])
        return ans;
    vis[sum] = true;
    for (int d = 1; d <= 6; ++d)
        ans = (ans + dp(sum - d) % MOD) % MOD;
    return ans;
}
int main(void)
{
    int n;
    cin >> n;
    cout << dp(n) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<ii> movies(n);
    for (auto &[e, s] : movies)
        cin >> s >> e;
    sort(movies.begin(), movies.end());
    set<ii> tavailable;
    for (int i = 1; i <= k; ++i)
        tavailable.emplace(0, i);
    int ans = 0;
    for (auto [e, s] : movies)
    {
        auto it = tavailable.upper_bound({s, 1e9});
        if (it != tavailable.begin())
        {
            --it;
            auto [free_time, ix] = *it;
            tavailable.erase(it);
            tavailable.emplace(e, ix);
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int main(void)
{
    int n;
    ll sum, ans;
    cin >> n;
    vi t(n);
    for (auto &ti : t)
        cin >> ti;
    sort(t.begin(), t.end(), greater<int>());
    sum = accumulate(t.begin() + 1, t.end(), (ll)0);
    ans = sum + max((ll)0, t[0] - sum) + t[0];
    cout << ans << endl;
    return 0;
}

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
int main(void)
{
    ll n;
    cin >> n;
    vpll tasks(n);
    for (auto &[a, d] : tasks)
        cin >> a >> d;
    sort(tasks.begin(), tasks.end());
    ll tim = 0, reward = 0;
    for (auto [a, d] : tasks)
    {
        tim += a;
        reward += d - tim;
    }
    cout << reward << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vii = vector<ii>;
int main(void)
{
    int n, last = 0, ans = 0;
    cin >> n;
    vii movies(n);
    for (auto &[s, e] : movies)
        cin >> s >> e;
    sort(movies.begin(), movies.end(), [](ii x, ii y) {
        return x.second < y.second;
    });
    for (auto [s, e] : movies)
    {
        if (last <= s)
        {
            last = e;
            ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const N = 7;
int const MOVES = 48;
bitset<4> const HORIZONTAL_T(string("1100"));
bitset<4> const VERTICAL_T(string("0011"));
string s;
bool visited[N][N];
vector<ii> const directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
inline bool in_bounds(int r, int c)
{
    return 0 <= r and r < N and 0 <= c and c < N;
}
inline bool valid(int r, int c)
{
    return in_bounds(r, c) and not visited[r][c];
}
bool tform(int r, int c, char dir)
{
    switch (dir)
    {
    case 'U':
        return not valid(r - 2, c) and valid(r - 1, c - 1) and
               valid(r - 1, c + 1);
    case 'D':
        return not valid(r + 2, c) and valid(r + 1, c - 1) and
               valid(r + 1, c + 1);
    case 'L':
        return not valid(r, c - 2) and valid(r + 1, c - 1) and
               valid(r - 1, c - 1);
    case 'R':
        return not valid(r, c + 2) and valid(r + 1, c + 1) and
               valid(r - 1, c + 1);
    default:
        return false;
    }
}
inline bool goal(int r, int c) { return r == N - 1 and c == 0; }
ll backtrack(int r, int c, int ix)
{
    if (goal(r, c) and ix != MOVES)
        return 0;
    if (ix == MOVES)
        return goal(r, c);
    ll ans = 0;
    visited[r][c] = true;
    if (s[ix] == '?' or s[ix] == 'L')
        if (valid(r, c - 1) and not tform(r, c, 'L'))
            ans += backtrack(r, c - 1, ix + 1);
    if (s[ix] == '?' or s[ix] == 'R')
        if (valid(r, c + 1) and not tform(r, c, 'R'))
            ans += backtrack(r, c + 1, ix + 1);
    if (s[ix] == '?' or s[ix] == 'U')
        if (valid(r - 1, c) and not tform(r, c, 'U'))
            ans += backtrack(r - 1, c, ix + 1);
    if (s[ix] == '?' or s[ix] == 'D')
        if (valid(r + 1, c) and not tform(r, c, 'D'))
            ans += backtrack(r + 1, c, ix + 1);
    visited[r][c] = false;
    return ans;
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> s;
    cout << backtrack(0, 0, 0) << endl;
    return 0;
}

using namespace std;
using ll = long long;
int const NMAX = 8;
bool reserved[NMAX][NMAX];
int queen_at_row[NMAX];
bool valid(int row, int col)
{
    if (reserved[row][col])
        return false;
    for (int r = 0, c = queen_at_row[0]; r < row; ++r, c = queen_at_row[r])
        if (c == col or abs(r - row) == abs(c - col))
            return false;
    return true;
}
ll backtrack(int row)
{
    if (row == NMAX)
        return 1;
    ll ans = 0;
    for (int col = 0; col < NMAX; ++col)
    {
        if (valid(row, col))
        {
            queen_at_row[row] = col;
            ans += backtrack(row + 1);
            queen_at_row[row] = 0;
        }
    }
    return ans;
}
int main(void)
{
    char ch;
    for (int r = 0; r < NMAX; ++r)
    {
        for (int c = 0; c < NMAX; ++c)
        {
            cin >> ch;
            reserved[r][c] = (ch == '*');
        }
    }
    cout << backtrack(0) << endl;
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 20 + 11;
int p[NMAX];
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, sum = 0, ans = INT_MAX;
    cin >> n;
    for (ll i = 0; i < n; i++)
    {
        cin >> p[i];
        sum += p[i];
    }
    for (ll mask = 0; mask < (1 << n); mask++)
    {
        ll cur = 0;
        for (ll i = 0; i < n; i++)
        {
            if (mask & (1 << i))
                cur += p[i];
        }
        ans = min(ans, abs(sum - cur - cur));
    }
    cout << ans;
    return 0;
}