Joey and Chandler have plans to go to the Knicks game. However , Joey also wants to try sandwiches from different restaurants before going. He needs to return on time so that Chandler and he can leave for the game. All the N restaurants lie on the same street at positions p[i] and Joey spends time t[i] at the respective restaurants. Joey takes 1 unit of time to travel 1 unit on the path i.e. to travel from position 1 to 3 , he takes 3-1 = 2 units of time. Assuming that Joey starts from 0 , and Chandler and he have to leave for the game in T seconds , can you tell what is the maximum number of restaurants that Joey can cover before leaving.

EXAMPLE Consider N = 3 , T = 10 and pi , ti = [{1,3} , {2,3}]

• If Joey goes to the first restaurant the total time consumed is 1(to travel) + 3(spent at restaurant) = 4. Time remaining = 10-4 = 6.
• Now if he goes to second restaurant , time taken = (to travel from 1) + 2(spent here) = 3. Time remaining = 6 — 3 = 3.
• For returning from here time taken is 2units. Time remaining = 3-2=1.

So the answer is 2.

dp[i][0] -> If he chooses not to stay at the restaurant but travel through here , we only consider time to reach here i.e. p[i]

dp[i][1] -> If he chooses to stay here , we take time spent here into consideration i.e. t[i]

At each position we will take 2 cases : when he decides to stay at the restaurant and when he just passes through this position. At each point we will also check if the total time taken + time to return back is less than or equal to T. If not so we will break from here as we cannot go ahead from here. (I have already sorted according to position).

int dp[n+1][2] , T0 = 0, T1 = 0 , ans = 0;
    dp[1][0] = 0 , T0 = inp[1].first;
    
    if(2 * inp[1].first + inp[1].second <= T) {
        dp[1][1] = 1 , T1 = inp[1].first + inp[1].second , ans++;
    } else {
        dp[1][1] = 0 , T1 = inp[1].first;
    }
    
    
    for(int i=2; i<=n; i++) {
        dp[i][0] = dp[i][1] = 0;
        
        //dp[i][0]
        if(T0 + 2 * inp[i].first - inp[i-1].first <= T) {
            dp[i][0] = max(dp[i][0] , dp[i-1][0]);
            T0 = T0 + inp[i].first - inp[i-1].first;
        } 
        
        if(T1 + 2 * inp[i].first - inp[i-1].first <= T) {
            dp[i][0] = max(dp[i][0] , dp[i-1][1]);
            T0 = T1 + inp[i].first - inp[i-1].first;
        }
        
        //dp[i][1]
        if(T0 + 2 * inp[i].first - inp[i-1].first + inp[i].second <= T) {
            dp[i][1] = max(dp[i][1] , dp[i-1][0] + 1);
            T1 = T0 + inp[i].first - inp[i-1].first + inp[i].second;
        } 
        
        if(T1 + 2 * inp[i].first - inp[i-1].first + inp[i].second <= T) {
            dp[i][1] = max(dp[i][1] , dp[i-1][1] + 1) ;
            T1 += inp[i].first - inp[i-1].first + inp[i].second;
        }
        
        else break;
        ans = max({ans , dp[i][1] , dp[i][0]});
    }