Rockstar Rock Dongho

Time limit2sMemory limit128 MB

Summary

Given counts of songs by their fast/slow start and end tempos, find the longest ordering of distinct songs into a valid chain that must begin with a fast-starting song if any exists.

Level: Medium6 of 10
Topics: Graph, Math, Greedy
Solved: No attempts yet

Problem

Rock Dongho is choosing songs for a new album. Each song has a starting tempo and an ending tempo, and each tempo is either fast (F) or slow (S). There are FF songs that start fast and end fast, FS songs that start fast and end slow, SF songs that start slow and end fast, and SS songs that start slow and end slow.

Each selected song may appear on the album at most once. The order of songs must satisfy the following conditions.

For every song except the first one, its starting tempo must be the same as the ending tempo of the song immediately before it.
If at least one recorded song starts fast, the first song on the album must start fast. If no recorded song starts fast, this condition does not apply.

Find the maximum number of songs Dongho can put on the album while satisfying all conditions.

Input

The first line contains four integers FF FS SF SS in that order. Each integer is between 0 and 1,000 inclusive, and at least one of them is positive.

Output

Print the maximum number of songs Dongho can put on the album while satisfying the conditions.

Examples4

Example 1
Input
```
1 2 1 1
```
Expected output
```
5
```
Example 2
Input
```
100 0 0 200
```
Expected output
```
100
```
Example 3
Input
```
0 0 20 200
```
Expected output
```
201
```
Example 4
Input
```
192 279 971 249
```
Expected output
```
999
```