组合幸运数字

const readline=require('readline');
const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
});
/*
 小易的幸运数字是7，现有一个整数数组 nums，
 请你找出并返回能被七整除的子集合的最大和，如果找不到则返回-1
 输入:
 一个正整数数组列表nums，用空格区分，1<=length(nums)<=100000，sum(nums) <= 1000000000
 */
rl.on('line',function (line) {
    /*1.处理数据*/
    let arr=line.trim().split(' ').map(Number);

    /*2.dp*/
    //由于是全是正整数,所以 sum >= arr.length
    let sum=arr.reduce((a,b)=>a+b);
    //dp[i]记录i是否能够得到 1为可得到,0则相反
    let dp=new Array(sum+1).fill(0);
    dp[0]=1; dp[sum]=1;
    /*这个方法很巧妙, 最初是a+b+c+d,每次从所有的满足条件的子集合减去一个数
    * 这样就很方便的得到了所有的排列*/
    for (let i=0;i<arr.length;i++){
        for (let j=0;j<=sum;j++){
            if (dp[j]===1&&j>=arr[i]){
                dp[j-arr[i]]=1;
            }
        }
    }

    let maxSum=-1;
    for (let i=dp.length-1;i>=7;i--){
        if (dp[i]===1&& i%7===0){
            maxSum=i;
            break;
        }
    }
    console.log(maxSum);
})