Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Cola

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTo celebrate the opening of the Winter Computer School the organizers decided to buy in *n* liters of cola. However, an unexpected difficulty occurred in the shop: it turned out that cola is sold in bottles 0.5, 1 and 2 liters in volume. At that, there are exactly *a* bottles 0.5 in volume, *b* one-liter bottles and *c* of two-liter ones. The organizers have enough money to buy any amount of cola. What did cause the heated arguments was how many bottles of every kind to buy, as this question is pivotal for the distribution of cola among the participants (and organizers as well).

Thus, while the organizers are having the argument, discussing different variants of buying cola, the Winter School can't start. Your task is to count the number of all the possible ways to buy exactly *n* liters of cola and persuade the organizers that this number is too large, and if they keep on arguing, then the Winter Computer School will have to be organized in summer.

All the bottles of cola are considered indistinguishable, i.e. two variants of buying are different from each other only if they differ in the number of bottles of at least one kind.

Input

The first line contains four integers — *n*, *a*, *b*, *c* (1 ≤ *n* ≤ 10000, 0 ≤ *a*, *b*, *c* ≤ 5000).

Output

Print the unique number — the solution to the problem. If it is impossible to buy exactly *n* liters of cola, print 0.

Examples

Input

10 5 5 5

Output

9

Input

3 0 0 2

Output

0

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/22/2018 19:29:39 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|