Under construction

Still being built. Things may change

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