TC : O ( n )

Let the answer be the longest subsequence starting with index "L" and ending with index "R"

It is given array A is increasing, Thus max ( a[l] , a[l+1], .... , a[r] ) = a[r]
the max part will be the rightmost index of the subsequence.

Now, The problem becomes ::

sum(b[l],b[l+1],...b[r]) <= ( s — a[r] )

name the above expression as req_sum

The given input structure hints that the question will be solved as we take inputs

IMAGINE THIS QUESTION AS IF A SNAKE IF MOVING IN A STRAIGHT LINE.

AT EVERY INDEX ITS LENGTH INCREASES (sum += b) .

IF ITS LENGTH INCREASES BEYOND A CERTAIN POINT ( req_sum ) , WE TRIM ITS TAIL ( sum -= b[l] ) TILL IT REACHES THE REQUIRED LENGTH.

AT EVERY INDEX WE RECORD THE LENGTH OF SNAKE ;)

CODE ::

******************************

n , s = input

B = [ ] (for storing array b)(no need for A)

sum_of_subsequence = 0

l = 0 , r = 0 (l , r are the makers of starting and ending index of sequence)

answer = 0 (answer is the maximum required length)

for ( i = 1 ; i <= n ; i++ )

a , b = input

req_sum = s - a

sum_of_subsequence += b

B.append(b)

r += 1

if sum_of_subsequence > req_sum :  (if sum exceeds required sum, we decrease it)

    while ( sum_of_subsequence > req_sum ) :

       sum_of_subsequence -= B[l]
       l += 1

length_of_subsequence = r - l

if ( length_of_subsequence > answer ):

    answer = length_of_subsequence

print ( answer )

********************************