덕분에 챌린지

[덕분에 챌린지]는 의료진들의 헌신에 감사를 표시하기 위해 중앙재난안전대책본부에서 시작한 캠페인이며, 유명인을 포함한 많은 사람들이 동참하고 있다. 챌린지에는 누구나 참여할 수 있으며, 존경을 뜻하는 수어를 사진으로 찍은 뒤 SNS에 올리고, 이어서 참여시킬 사람을 지목하면 된다.

[덕분에 챌린지]에 참여하고 싶어하는 $N+M$ 명의 사람이 있다. 이들 중 한 명이 챌린지를 시작하여 다음으로 참여할 사람을 두 명 이하로 지목하고, 지목받은 사람이 챌린지를 이어 나가는 방식으로 챌린지에 참여하려고 한다. 이때, 이미 챌린지를 완료했거나 다른 사람에 의해 지목된 사람은 지목하지 않는 것으로 하자. 즉, 한 사람은 한 번만 지목될 수 있다. 또한, 챌린지를 처음 시작할 한 명을 제외한 사람이 챌린지에 참여하기 위해서는 반드시 다른 사람에 의해 지목되어야 한다.

각 사람이 챌린지를 시작하여 완료하기까지 걸리는 시간이 정해져 있다. 다음으로 참여할 사람을 지목하는 것은 챌린지를 완료한 순간 이루어지며, 지목받은 사람은 그 순간 챌린지를 시작하게 된다. $N+M$ 명의 사람 중 $N$ 명은 챌린지를 하는 데 $X$의 시간이 필요하고, 나머지 $M$ 명은 $Y$의 시간이 필요하다. 모든 사람이 챌린지를 완료하기 위해 필요한 시간의 최솟값을 구하여라.

입력 형식

첫 줄에 네 개의 정수 $N$, $M$, $X$, $Y$가 공백으로 구분되어 주어진다. $(0 \le N, M \le 500;$ $1 \le X, Y \le 1\,000\,000;$ $N+M \ge 1)$

출력 형식

첫 줄에 모든 사람이 챌린지를 완료하기 위해 필요한 시간의 최솟값을 출력한다.

예제

4 1 2 5

7

예제 설명

다섯 명의 사람 $A$, $B$, $C$, $D$, $E$가 있는데, 사람 $A$, $B$, $C$, $D$는 챌린지를 하는 데 시간 $2$가 필요하고, 사람 $E$는 시간 $5$가 필요한 상황이다. 다음과 같은 과정을 통해 모든 사람이 챌린지를 완료할 수 있고, 이때 필요한 시간은 $7$이며, 이보다 더 빠르게 챌린지를 완료할 수 없다.

1. 시간 $0$에 $A$가 챌린지를 시작한다.
2. 시간 $2$에 $A$가 챌린지를 완료하고, $B$와 $E$를 지목한다.
3. 시간 $4$에 $B$가 챌린지를 완료하고, $C$와 $D$를 지목한다.
4. 시간 $6$에 $C$와 $D$가 챌린지를 완료한다.
5. 시간 $7$에 $E$가 챌린지를 완료한다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설