Shomtring

Time limit2sMemory limit128 MB

Summary
Given limits on total A's, total B's, and the longest allowed run of each, compute the maximum length string built only from A and B.
Level

Medium6 of 10

Topics
Greedy, Math, Implementation
Solved
No attempts yet

Problem

A string made only of the characters A and B is called a Shomtring if it satisfies all of the following conditions.

  • It uses at most countA characters A.
  • It uses at most countB characters B.
  • Every contiguous block made only of A has length at most maxA.
  • Every contiguous block made only of B has length at most maxB.

Given countA, countB, maxA, and maxB, find the maximum possible length of a Shomtring.

Input

The first line contains four integers countA, countB, maxA, and maxB. Each value is between 0 and 1,000,000, inclusive.

Output

Print the maximum possible length of a Shomtring.

Examples4

  1. Example 1

    Input
    3 5 1 1
    Expected output
    7

  2. Example 2

    Input
    0 0 10 10
    Expected output
    0

  3. Example 3

    Input
    10 10 0 0
    Expected output
    0

  4. Example 4

    Input
    677578 502524 989951 504698
    Expected output
    1180102