Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Water

By borisal · Limits 2s, 256 MB

Dhoni has 3 types of water bottles. He has exactly aa bottles of volume 0.5 liters, bb bottles of volume 1 liter, and cc bottles of volume 2 liters. Your task is to help Dhoni count the number of ways to carry exactly nn liters of water. Two variants are different from each other only if they differ in the number of bottles of at least one kind.

Input

The first line will contain four integers — n, a, b, c (1n30000, 0a,b,c10000)n, a, b, c (1 \leq n \leq 30000, 0 \leq a, b, c \leq 10000).

Output

Print one number — the solution to the problem. If it is not possible to make exactly nn liters of water, print 00.

Samples

InputOutput
10 5 5 5 
9
InputOutput
3 0 0 2
0

    Discussion

    Statistics


    95% Solution Ratio

    TonimaEarliest, 1w ago

    BruisedYetOkayFastest, 0.0s

    Noshin_1703086Lightest, 131 kB

    FrdhsnShortest, 283B

    Submit

    Login to submit

    Editorial

    First of all, we will generate all possible combinations of “aaa”(0.50.50.5-liter bottle) and “bbb”(...

    Toph uses cookies. By continuing you agree to our Cookie Policy.