Лифты (30 баллов)
Автор задачи: Ефимов А.Е.
Задачу добавил: alef
Успешно сдано решений: 5
Наконец, NN приехал в город ММ, и теперь ему предстоит поселиться на время семинара в общежитии УУУ. В этом общежитии есть N лифтов из которых M даже работают (лестницы в архитектуре здания не предусмотрены). Каждый лифт вмещает до К человек, но когда он приезжает, войти в него успевает только 1 человек, поскольку после этого лифт мгновенно закрывает свои двери (выйти успевают все желающие).
Известна скорость движения лифта (E этажей в час, для всех лифтов она одинакова), а также количество людей на каждом этаже в начальный момент времени и то, на какой этаж они хотят приехать. Определить, сколько времени пройдет, прежде чем все они попадут на нужный им этаж.
Известно расположение лифтов на этажах в начальный момент времени. Все они сначала начинают двигаться вверх, при движении останавливаются на каждом этаже. Когда лифты достигают последнего этажа, они начинают двигаться вниз, а когда достигают первого этажа - начинают двигаться вверх.
Формат входного файла input.txt
Первая строка - четыре целых числа: M (1<=M<=20) - количество работающих лифтов, E (1<=E<=1000) - скорость лифта, измеренная в этажах в час, K (1<=K<=10) - максимальное количество человек, которое вмещает лифт, и H (1<=H<=20) - количество этажей в здании.
Вторая строка - M целых чисел через пробел, каждое из которых отвечает номеру этажа, на котором в начальный момент времени расположен каждый из М лифтов.
Каждая из последующих H строк содержит номер этажа, на который хотят попасть ожидающие лифт люди, находящиеся на данном этаже, и их количество Q (0<=Q<=15) (третья строка во входном файле содержит номер этажа, на который хотят попасть люди, находящиеся на первом этаже, и их количество, четвертая - на втором и т.д.)
Формат выходного файла output.txt
Время, которое требуется, чтобы все попали на нужный этаж, в формате <часы>:<минуты>
Пример входного файла
2 3 4 5
1 2
4 1
5 1
1 1
5 1
4 1
Пример выходного файла
02:20