1 second

256 megabytes

standard input

standard output

Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

• After the cutting each ribbon piece should have length a, b or c.
• After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3.

In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 2.

/* ***********************************************

Author        :guanjun

Created Time  :2016/10/7 18:22:02

File Name     :cf119a.cpp

************************************************ */

#include <bits/stdc++.h>

#define ull unsigned long long

#define ll long long

#define mod 90001

#define INF 0x3f3f3f3f

#define maxn 10010

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << ;

const double eps=1e-;

using namespace std;

priority_queue<int,vector<int>,greater<int> >pq;

struct Node{

    int x,y;

};

struct cmp{

    bool operator()(Node a,Node b){

        if(a.x==b.x) return a.y> b.y;

        return a.x>b.x;

    }

};

bool cmp(int a,int b){

    return a>b;

}

int dp[];

int main()

{

    #ifndef ONLINE_JUDGE

    //freopen("in.txt","r",stdin);

    #endif

    //freopen("out.txt","w",stdout);

    int n,a,b,c;

    while(cin>>n>>a>>b>>c){

        cle(dp);

        dp[a]=dp[b]=dp[c]=;

        for(int i=;i<=n;i++){

            if(i>a&&dp[i-a])dp[i]=max(dp[i],dp[i-a]+);

            if(i>b&&dp[i-b])dp[i]=max(dp[i],dp[i-b]+);

            if(i>c&&dp[i-c])dp[i]=max(dp[i],dp[i-c]+);

        }

        cout<<dp[n]<<endl;

    }

    return ;

}