영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
While hunting monsters, the brave hunter encounters a Hydra. But this was not just any Hydra - this is an RGB Hydra!
This terrifying creature can have heads of three different colors. Initially, the Hydra has:
- R red heads,
- G green heads, and
- B blue heads.
Each time the hunter cuts off a head of a particular color, two new heads instantly grow back - one of each of the other two colors. For example, if the hunter cuts off a red head, then a green and a blue head will grow back immediately.
Driven by courage and ambition, the hunter not only wants to defeat the Hydra but also leave a lasting trace of the journey. To do this, the hunter wants as much red as possible to be visible on the Hydra - the goal is to maximize the number of red heads cut off!
Before the Hydra launches its attack, the hunter has enough time to make at most k moves, where each move involves cutting off a single head.
What is the maximum number of red heads the Hydra can have after at most k moves?
Input
The input consists of a single line containing four integers R, G, B, and k (0 ≤ R, G, B, k ≤ 10^18), where:
- R is the number of red heads,
- G is the number of green heads,
- B is the number of blue heads,
- k is the maximum number of moves the hunter can perform.
It is guaranteed that the Hydra has at least one head initially, i.e., R + G + B ≥ 1.
(Note that the numbers R, G, B, k are very large, and in languages like C++, you will need to use long long instead of int.)
Output
Print a single integer: the maximum number of red heads the Hydra can have after at most k moves.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | R, G, B, k ≤ 10 |
| 2 | 15 | k ≤ R, G, B |
| 3 | 10 | R = 0 |
| 4 | 10 | G = 0 |
| 5 | 10 | B = 0 |
| 6 | 35 | No additional constraints. |
Explanation of Samples
The Hydra initially has only 1 blue head, and the hunter can make at most 1 move. The only move that can be made is to cut off the blue head, which results in 1 red head and 1 green head. No more moves can be performed, which means that 1 red head is the maximum number.
The Hydra has 4 red heads, 3 green heads, and 2 blue heads, and the hunter can make at most 1 move. The hunter can, for example, choose to cut off a green head, which results in 5 red heads, 2 green heads, and 3 blue heads. After this move, no further moves can be performed. There is no way to get more than 5 red heads, so the answer is 5.
The Hydra has 10 heads of each color. Since the hunter cannot make any moves (as k = 0), the number of red heads remains 10.
예제
예제 1
0 0 1 1
1
예제 2
4 3 2 1
5
예제 3
10 10 10 0
10
예제 4
926332030620250124 57836736120250125 503852839920250126 804672315982687419
1731004346602937543