Задача №111293. Чай
Члены жюри Всероссийской командной олимпиады школьников по программированию очень любят пить чай. Но, к сожалению, в их распоряжении всего один чайник, имеющий объем \(v\) мл. Работа жюри хорошо отлажена, поэтому точно известно, кто и когда отправиться пить чай, и сколько воды ему для этого нужно.
Рассмотрим действия, предпринимаемые членами жюри для получения желанного напитка.
Когда человек из жюри подходит к чайнику, то если никого больше у чайника нет, он смотрит, достаточно ли в чайнике воды. Если в чайнике не хватает воды для этого человека, то он доливает в чайник воды до полного объема в \(v\) мл. Если же воды достаточно, то вода в чайник не доливается. После этого чайник включается и доводит воду до температуры 100 градусов. После этого член жюри наливает себе необходимый объем кипятка для заварки чая и отходит от чайника.
Если в момент прихода к чайнику член жюри обнаруживает других людей, ожидающих кипятка, то он становится в очередь и дожидается, пока все предыдущие люди выполнят свои действия с чайником.
Температура кипения воды составляет 100 градусов Цельсия. Мощность чайника составляет \(N\), что означает, что если в чайнике \(x\) мл воды, то температура воды в чайнике изменяется по формуле \(T(t) = T_0 + \frac{Nt}{x}\), где \(T_0\) — температура воды в момент включения чайника, а \(t\)~— время в секундах, прошедшее с момента включения чайника. Когда температура воды достигает 100 градусов, чайник автоматически выключается.
Когда чайник выключен, вода в нем начинает остывать. Вне зависимости от количества жидкости в чайнике, температура воды падает со скоростью \(k\) градусов в секунду. Когда вода достигает комнатной температуры в 20 градусов, остывание прекращается.
Заливаемая в чайник вода имеет комнатную температуру 20 градусов. При доливании воды в чайник температура воды усредняется, а именно, если в чайнике было \(w\) мл воды температуры \(T\), то температура воды в чайнике после его заполнения станет \(\frac{wT + 20(v-w)}{v}\).
Известны времена, когда члены жюри идут пить чай, а также количество кипятка им необходимое. Требуется для каждого члена жюри вывести в какой момент он начнет пить чай. Считается, что разливают воду по чашкам и заваривают чай члены жюри моментально, при этом всегда наливая себе ровно необходимый им объем. Изначально чайник пуст.
Первая строка входного файла содержит четыре целых числа \(m\), \(v\), \(N\) и \(k\) (\(1 \le m \le 100\,000\), \(1 \le v, N, k \le 1000\)) — количество членов жюри, пьющих чай, объем чайника в мл, мощность чайника и скорость остывания воды в чайнике. Далее следуют \(m\) строк — описания людей, пьющих чай. В каждой строке два целых числа \(t_i\) и \(a_i\) (\(1 \le t_i \le 10^6\); \(1 \le a_i \le v\)) — время в секундах от начала олимпиады, когда член жюри отправиться пить чай, и необходимый ему объем воды в мл. Никакие два члена жюри не отправляются пить чай одновременно.
В выходной файл выведите \(m\) строк по одному числу в каждой — время в секундах от начала олимпиады, когда соответствующий член жюри начнет пить чай. Ответ должен иметь абсолютную или относительную погрешность не более \(10^{-7}\).
3 1000 200 1 1 500 501 300 551 300
401.0 701.0 1021.0