Indian Computing Olympiad Archives 2011

Related:

Zonal Computing Olympiad 2011, 4 Dec 2010

10:00 am–1:00 pm IST

Problem 1 : Hyper Mall

There are M shoppers, numbered 1,2,…,M at the Siruseri HyperMall today. We have information on the precise time at which each shopper will complete his/her shopping and arrive at the billing centre. No two shoppers arrive at the billing centre at the same time. At the billing centre they enter at the rear end of a queue.

There are C counters, numbered 1,2,…,C at the billing centre. When a shopper reaches the head of the queue he waits for some counter to be available and then moves to such a counter. If multiple counters are available he chooses the one with lowest number. We also have information on the amount of time each shopper takes at the billing counter.

Let t_i be the time at which shopper i finishes his/her shopping and arrives at the billing centre and let b_i be the amount of time he/she will take at the billing counter, where both t_i and b_i are integers. Your task is to determine the time at which the last shopper leaves the HyperMall.

Here is an example with 4 shoppers and 2 counters. The table below lists the values t_i and b_i for the 4 shoppers.

i	1	2	3	4
t_i	9	7	8	10
b_i	20	14	12	11

The first to arrive at the billing center is shopper 2, who goes to counter 1. The next to arrive is shopper 3, who immediately goes to counter 2. When the next shopper, shopper 1, arrives, both the counters are occupied and hence he stands in the queue. Subsequently, shopper 4 arrives and finds both counters occupied, and hence stands behind 1 in the queue. At time 20, shopper 3 finishes and so shopper 1 moves to counter 2. At time 21, shopper 2 finishes his billing and shopper 4 moves to counter 1. Shopper 4 leaves at time 32 and, finally, shopper 1 leaves at time 40.

Input format

The first line of input contains two integers giving the number of shoppers N and the number of counters C. This is followed by N lines each containing two integers, the values t_i and b_i for the N shoppers.

Output format

A single line with a single integer indicating the time at which the last shopper leaves the HyperMall.

Testdata

You may assume that 1 ≤ N ≤ 100 and 1 ≤ C ≤ 50. You may assume that all input data and the final answer can be stored in variables of type int.

Sample Input

Sample Output

Time and memory limits

The time limit for this task is 1 second. The memory limit is 32MB.