Atspėk skaičių!

시간 제한1초메모리 제한1024 MB

요약

1부터 N까지의 숨은 수를 맞히는 게임에서, 너무 큰 추측마다 D점, 너무 작은 추측마다 M점을 아르투라스가 얻는다. 비타우타스가 항상 이기도록 추측 전략을 구현한다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 게임 이론, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Artūras ir Vytautas žaidžia skaičių spėjimo žaidimą.

Pirmiausia, Artūras sugalvoja skaičių $A$ nuo $1$ iki $N$ . Tada Vytautas spėja skaičių. Jei Vytautas spėjo per didelį skaičių, Artūras gauna vienokį kiekį taškų, o jei per mažą – kitokį. Žaidimas baigiasi, kai Vytautas atspėja skaičių.

Sakykime, Vytautas spėjo skaičių $V$ , tada taškai dalinami šitaip:

jei $V > A$ , Artūras gauna $D$ taškų;
jei $V < A$ , Artūras gauna $M$ taškų;
jei $V = A$ , Vytautas gauna $T$ taškų ir žaidimas baigiasi.

Artūras laimi, jei surenka daugiau taškų nei Vytautas. Kitu atveju laimi Vytautas.

Artūras labai nori laimėti, todėl kartais sukčiauja. Iš pradžių nesugalvoja skaičiaus, o savo skaičių derina prie Vytauto klausimų. Artūras nenori būti pagautas, todėl neduoda prieštaringos informacijos, t. y. visada bus nors vienas skaičius, atitinkantis visus Artūro kol kas duotus atsakymus.

Kadangi Vytautas labai mėgsta varžytis, jis nori laimėti bet kokiu atveju. Todėl jis pasirinko parametrus $N$ , $M$ , $D$ ir $T$ taip, kad visada galėtų laimėti, kad ir kokį skaičių Artūras sugalvotų.

Parašykite programą, kuri žaisdama už Vytautą laimėtų žaidimą.

제한

$1 ≤ N ≤ 10^{18}$
$100 ≤ M, D ≤ 100\\,000$
$0 ≤ T ≤ 10\\, 000\\, 000$

예제1

예제 1
입력
```
10 100 200 1000

d

m

g
```
예상 출력
```
8

5

6
```