2015 Mock CCC by Alex and Timothy

Problem S1: Dupvoting

Currently, one of the most popular social news websites is seddit. On seddit, one user can submit a link to content while other users can say things in the comments. A great news aggregator like this is community-driven. Naturally, it employs a system where users can review and rate content. Many websites, including seddit, use a voting system where each user can give a submission either an upvote (worth +1 point) or a downvote (worth −1 point). The score of a submission is therefore the total points across all users who have voted on it.

Recently, seddit is trying a new system where a new "dupvote" button is introduced. It's simple, really – if an upvote contributes +1 to the net score of a submission, then a dupvote simply contributes +2 to the net score. The downvote buttom still works as expected. This system will allow users to express support for quality content that's really exceptional.

As an avid user of seddit, you really enjoy this new system, but you are unsatisfied with one aspect of the site. For a given post, the site displays its net points P (−2000 ≤ P ≤ 2000) and the number of users U (3 ≤ U ≤ 1000) that have voted on the content. However, you have no idea what ratio of these votes are dupvotes, upvotes, or downvotes.

The hacker in you decided to analyse the site's JavaScript. To your amusement, you've discovered a little bug which allows you to see a simple ratio R1:R2 (1 ≤ R1, R2 ≤ 1000) for each post. You know that this is a ratio of two of the values in the number of dupvotes, upvotes, and downvotes, but you don't know anything about which two. For a given post, you would like to calculate all possible triplets for the number of dupvotes, upvotes, and downvotes that could make up the total net points for that post.

Input Format

Line 1 of input will contain a single integer P, the net points on the post.
Line 2 of input will contain a single integer U, the number of users that have voted.
Line 3 of input will contain a single integer R1, the first number in the ratio.
Line 4 of input will contain a single integer R2, the second number in the ratio.

Output Format

Output a single integer, the number of possible combinations of dupvotes, upvotes, and downvotes that can result in a net score of P points on the post. It is guaranteed that all three of these values are positive.

Sample Input


Sample Output


Explanation of Sample

The net score on the post is +2 as a result of 5 users voting. It is guaranteed that a ratio of 2:1 exists between either the dupvotes and upvotes, dupvotes and downvotes, or upvotes and downvotes. If there is 1 dupvote, 2 upvotes, and 2 downvotes, then the net score would be +2 and the ratio of upvotes to dupvotes would be 2:1. In fact, this is the only solution.

All Submissions
Best Solutions

Point Value: 5
Time Limit: 1.00s
Memory Limit: 64M
Added: Feb 18, 2015
Authors: Alex, FatalEagle

Languages Allowed:

Comments (Search)

It's quiet in here...