|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||128 MB||1||0||0||0.000%|
After the programming contest team MSX decides to grab a bite at the Burger King. It turns out it's a rather busy evening there: each counter has a queue of people waiting to order their meals and more people keep pouring in. Since they're rather hungry from a long day of programming, team MSX wants to order food as soon as possible.
Team member Menno suggests that, in order to get their food as fast as possible, they should join the shortest queue. Team member Sarah disagrees: she notices that some employees are considerably slower than their colleagues, hence the team should join the queue of the fastest employee. Team member Xenon, however, notices that every now and then, some employees switch with their colleagues. If a customer was being helped during the change, this takes time, since the new employee has to start all over again in helping the customer. If the customer's order would have been finished at the moment of the change, though, the customer's order is finished first and the new employee immediately continues serving the next customer without delay. Besides that, the service speed is also dependent on the type of customer: a family takes considerably more time to help than a middle-aged man.
Team MSX decides it's best to work dynamically. All team members have a strong predictive ability, which allows them to know how much time an employee will need to help a certain customer. As they enter the Burger King, they calculate for each queue hoe long it will take until all customers in that queue have been helped. They then join the queue that will be the first one to be empty. When the situation changes, for example when the employee at a counter changes, they reevaluate which queue they should join to be able to order as soon as possible. If it turns out it's more effective to join another queue, they will not hesitate. If team MSX has to choose from multiple queues that would be equally effective, they choose the queue with the lowest identification number, unless they're in one of those queues themselves, in which case they will not switch queues. Of course, when the team switches queues, they join the end of the new queue. The switching itself takes no time at all.
Given a set of employees, queues of customers and a schedule of events, figure out how many minutes it takes before the team can order their well-earned diner if they choose their queues optimally.
No more than one event takes place in the same minute. In addition, there will never be more than 30 customers in a queue (excluding team MSX) at any time.
For each test case the output contains one line with a single integer: the number of minutes team MSX needs to wait before they can order their food.
1 2 0 4 2 4 2 6 2 1 6 3 1 2 1 1 3 1 6 join 1 1 3 join 4 1 4 join 6 0 10 join 8 1 8 change 2 1 2 change 5 0 4