문제

성현이는 정확히 $M$ 단위의 물을 얻어야 한다. 하지만 성현이가 가진 도구는 각각 정수 용량 $X$와 $Y$를 가진 두 개의 물통뿐이다. 처음에는 두 물통 모두 비어 있다.

성현이는 다음 세 가지 연산 중 하나를 최대 $K$번 수행할 수 있다:

• 어느 한 물통을 가득 채운다.
• 어느 한 물통을 완전히 비운다.
• 한 물통의 물을 다른 물통에 붓는다. 이 연산은 부으려는 물통이 비거나, 받는 물통이 가득 찰 때까지 진행한다.

성현이는 두 물통에 담긴 물의 총합을 정확히 $M$으로 만들지 못할 수도 있다. 성현이가 최대 $K$번의 연산을 통해 만들 수 있는 물의 총합을 $M'$이라고 할 때, $|M - M'|$의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 네 정수 $X, Y, K, M$이 공백으로 구분되어 주어진다. ($1 \le X, Y \le 100$; $1 \le K \le 100$; $1 \le M \le 200$)

출력

성현이가 만들 수 있는 물의 총량 $M'$과 $M$의 차이 $|M - M'|$의 최솟값을 출력한다.

예제 입력 1

14 50 2 32

예제 출력 1

18