189A.md (1319B)
1 Source: https://codeforces.com/problemset/problem/189/A 2 3 A. Cut Ribbon 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Polycarpus has a ribbon, its length is *n*. He wants to cut the ribbon in a way that fulfils the following two conditions: 22 23 * After the cutting each ribbon piece should have length *a*, *b* or *c*. 24 * After the cutting the number of ribbon pieces should be maximum. 25 26 Help Polycarpus and find the number of ribbon pieces after the required cutting. 27 28 Input 29 30 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. 31 32 Output 33 34 Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists. 35 36 Examples 37 38 Input 39 40 ``` 41 5 5 3 2 42 ``` 43 44 Output 45 46 ``` 47 2 48 ``` 49 50 Input 51 52 ``` 53 7 5 5 2 54 ``` 55 56 Output 57 58 ``` 59 2 60 ``` 61 62 Note 63 64 In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3. 65 66 In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 2.