Question

"Solution"

A software company has N different projects, each with a certain number of API files. Currently, it is production time, all the projects are to be updated on live production and this is to be done by executing API files for all the projects, As projects are inter$-$connected, there is a condition to execute all the project's API files. Each project contains a number of API files and a blockage count B$,$ where the blockage count shows that if the current project is executed then the next upcoming B projects cannot be executed at that point in time. The production team wishes to know the maximum total number of API files that can be executed during the first execution while satisfying the given.condition.

Write an algorithm to find the maximum total number of API files that can be executed during the first execution while satisfying the given condition.

Input

The first line consists of two space separated integers projects row and project, col, representing the number of projects $($N$)$ and the number of details given for eachproject $($M$),$ where M is always $2.$ The next N line consists of M space$-$ separated integers representing the number of API files in each project and the blockage count $($P$).$

Output

Print an Integer representing the maximum total number of API files that can be executed during the first execution while satisfying the given condition.

Example

Input:

$42$

$21$

$32$

$33$

$14$

Output:

$5$

Explanation:

The maximum total API files can be executed by executing projects $1$ and $3.$

Execute project $1$: $2$ API files are executed, and the next project cannot be executed, that is project $2$

Unable to execute project $2.$Execute project $3$: $3$ API files are executed, and the remaining projects cannot be executed as the remaining project is one and the blockage count for the current project is $3.$

Total API files executed: $2+3=5.$ There is no other way to execute $5$ or more API files. Therefore, the output is $5.$ import java.io$.$BufferedReader;

import java.io$.$InputStreamReader;

import java.util.Scanner;

class Solution

$\{$

public static void main$($String args$[])$

$\{$

$//$ write your code here

$\}$