카오스 교수

카오스 교수의 비밀 실험실에서 위험한 박테리아를 배양하는 실험이 진행된다. 실험 첫째 날이 시작될 때 카오스 교수에게는 $a$마리의 위험한 박테리아가 있다.

실험의 하루는 다음과 같이 진행된다. 이른 아침에 교수는 컨테이너에서 모든 박테리아를 꺼내어 인큐베이터에 넣고, 그곳에서 박테리아가 분열하기 시작한다. 박테리아 한 마리마다 $b$마리의 새로운 박테리아가 생긴다.

인큐베이터에서 박테리아를 꺼낸 뒤, 그중 $c$마리를 여러 실험에 사용한 다음 폐기한다. 인큐베이터에서 꺼낸 박테리아가 $c$마리보다 적으면, 남아 있는 모든 박테리아를 실험에 사용하고 실험은 끝난다.

하루가 끝날 때 남은 박테리아는 컨테이너에 넣고 실험에 계속 사용해야 한다. 그러나 컨테이너에는 $d$마리까지만 넣을 수 있으므로, 남은 박테리아가 $d$마리보다 많으면 $d$마리를 컨테이너에 넣고 나머지는 폐기한다.

이제 카오스 교수는 실험이 $k$번째 날까지 끝난 뒤 컨테이너에 남아 있는 위험한 박테리아가 몇 마리인지 알고 싶어 한다. 이 질문에 대한 답을 구하자.

입력 파일의 유일한 줄에 다섯 개의 정수 $a$, $b$, $c$, $d$, $k$가 주어진다 ($1 \le a, b \le 1000$, $0 \le c \le 1000$, $1 \le d \le 1000$, $a \le d$, $1 \le k \le 10^{18}$).

$k$번째 날이 끝날 때 카오스 교수에게 있는 박테리아 수를 하나의 수로 출력한다. 실험이 $k$번째 날이나 그 이전에 끝나면 0을 출력한다.