1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxN = 21, maxX=101;
int main(){
    int n, x;
    while (~scanf("%d%d", &n, &x)){
        int a[maxN], sum[maxN] = { 0 };
        for (int i = 1; i <= n; i++){
            scanf("%d", a + i);
            sum[i] = sum[i - 1] + a[i];
        }
        if (sum[n] < x){
            printf("-1\n");
            continue;
        }
        int dp[maxN][maxX] = { 0 };
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= min(sum[i], x); j++){
                dp[i][j] = min(sum[i], dp[i - 1][max(0, j - a[i])] + a[i]);
                if (sum[i - 1] >= j){
                    dp[i][j] = min(dp[i][j], dp[i - 1][j]);
                }   
            }
        }
        printf("%d\n", dp[n][x]);
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX