Farmer John nhận được một đơn đặt hàng đúng \(M\) đơn vị sữa (\(1 \leq M \leq 200\)) và cần giao ngay. Không may, chiếc máy vắt sữa hiện đại của ông vừa bị hỏng, và ông chỉ có hai chiếc xô đựng sữa với dung tích nguyên là \(X\) và \(Y\) (\(1 \leq X,Y \leq 100\)) để đong sữa. Ban đầu, cả hai chiếc xô đều rỗng. Với hai chiếc xô này, ông có thể thực hiện tối đa \(K\) thao tác thuộc các loại sau (\(1 \leq K \leq 100\)):

• Đổ đầy hoàn toàn một trong hai chiếc xô.
• Đổ hết sữa khỏi một trong hai chiếc xô.
• Rót sữa từ một chiếc xô sang chiếc còn lại, dừng lại khi chiếc xô thứ nhất rỗng hoặc chiếc xô thứ hai đầy (tùy điều nào xảy ra trước).

Mặc dù FJ biết rằng có thể tổng lượng sữa trong hai chiếc xô cuối cùng không đúng bằng \(M\), hãy giúp ông tính sai số nhỏ nhất giữa \(M\) và tổng lượng sữa trong hai chiếc xô. Nói cách khác, hãy tính giá trị nhỏ nhất của \(|M-M'|\) sao cho FJ có thể tạo ra tổng cộng \(M'\) đơn vị sữa trong hai chiếc xô.

Dữ liệu vào

Dòng duy nhất chứa \(X\), \(Y\), \(K\) và \(M\).

Dữ liệu ra

In khoảng cách nhỏ nhất từ \(M\) đến một lượng sữa mà FJ có thể tạo ra.

Ví dụ

14 50 2 32

18

(0, 0) = 0 đơn vị
(14, 0) = 14 đơn vị
(0, 50) = 50 đơn vị
(0, 14) = 14 đơn vị
(14, 36) = 50 đơn vị
(14, 50) = 64 đơn vị

Nguồn

USACO 2016 February Contest, Silver - Milk Pails: https://usaco.org/index.php?page=viewproblem2&cpid=620

Tác giả: Brian Dean.