Tèo là chủ một trang trại, cô ấy nuôi con mèo và thuê người chăm sóc. Trong trang trại có một con đường thẳng, bên đường có ngọn đồi, được đánh số từ đến . Khoảng cách giữa ngọn đồi thứ và ngọn đồi thứ là . Những người chăm sóc đều sống ở ngọn đồi số .
Một ngày nọ, những chú mèo đi ra ngoài chơi. Con mèo thứ đi đến ngọn đồi chơi, chơi đến thời điểm thì dừng lại và đợi người chăm sóc đến đón tại chỗ. Những người chăm sóc phải thu hồi tất cả các con mèo. Mỗi người chăm sóc đi dọc theo con đường từ ngọn đồi số đến ngọn đồi số , đón tất cả những con mèo đã chờ sẵn trên các ngọn đồi. Người chăm sóc đi bộ trên đường cần thời gian, với vận tốc là mét trên mỗi đơn vị thời gian. Thời gian đón mèo trên mỗi ngọn đồi có thể bỏ qua, và số lượng mèo có thể mang theo là vô hạn.
Ví dụ, có hai ngọn đồi cách nhau đơn vị, một con mèo chơi ở ngọn đồi số và bắt đầu đợi từ thời điểm . Nếu người chăm sóc xuất phát từ ngọn đồi số vào thời điểm hoặc , anh ta có thể đón được mèo (đến đồi 2 vào thời điểm hoặc ), thời gian chờ đợi của mèo sẽ là hoặc . Nhưng nếu anh ta xuất phát vào thời điểm , anh ta sẽ đi qua ngọn đồi số vào thời điểm , lúc đó mèo vẫn đang chơi nên không thể đón được.
Nhiệm vụ của bạn là lập kế hoạch thời gian xuất phát từ ngọn đồi số cho mỗi người chăm sóc, sao cho tổng thời gian chờ đợi của tất cả các con mèo là nhỏ nhất. Thời gian xuất phát của người chăm sóc có thể là số âm.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên .
Dòng thứ hai chứa số nguyên dương , biểu thị khoảng cách giữa ngọn đồi thứ và ngọn đồi thứ là (lần lượt là ).
