Jesse is building his own operating system and now faces the task of building the process scheduling and the memory management feature. He has laid down the rules of how he is going to do it. It's as follows:
If a process needs to be executed and memory is available, the process is given the required amount of memory.
If a process needs to be executed and memory is not available, Jesse will wait until a few processes are completed which will free up enough memory and then he will assign it to the process.
Once a process is assigned some memory, it can't be removed from the memory until it's completed.
The processes should be executed in the given order. A process can't be allocated memory before process , if .
Jesse is busy with other stuff and needs your help in implementing this. Can you help him do this?
The time taken to allocate memory to a process is .
Note: In this problem you can modify at most three lines of code and you cannot add any new lines.
To restore the original code in the editor, create a new buffer by clicking on the top left icon in the editor.
Input Format
The first line contains two integers and , where is the number of processes and is the amount of memory available initially. Then lines follow, each line contains two integers and where is the time needed for the current process to complete and is the amount of memory it needs.
Constraints
Output Format
Print in a single line, the total time taken to execute all the given processes.
Sample Input
5 20
5 10
6 11
4 8
2 9
3 10
Sample Output
14
Explanation
The first process starts at time and utilizes units of memory. The second process can't start at time because it needs units of memory but only units is available. The second process starts at time and even the third process starts at the same time and in total both occupy units of memory. The third process finishes at time and the fourth process starts at time . The second and the fourth process end at time and the fifth process starts at and ends at time . So the answer is 14.