Minimum Time to Complete Tasks

You are given n tasks and m resources. Each task is specified by a start time s and a duration d. A resource can begin a task only when it is free and at or after its start time. Once a resource starts a task, it will be busy until the completion time which is computed as \(T = \max(\text{finish time}, s) + d\). The objective is to schedule all tasks using the available resources so that the completion time of the last task is minimized.

Hint: Use a min-heap to simulate the resources. Always assign the next task to the resource that becomes free the earliest.

inputFormat

The input is given via stdin in the following format:

• The first line contains two integers n and m — the number of tasks and the number of available resources.
• The next n lines each contain two integers s and d, where s is the start time of a task and d is its duration.

outputFormat

Output a single integer to stdout representing the minimum time by which all tasks can be completed.## sample

3 2
1 5
2 1
3 7

10