You are the head of a large enterprise. $n$ people work at you, and $n$ is odd (i. e. $n$ is not divisible by $2$).

You have to distribute salaries to your employees. Initially, you have $s$ dollars for it, and the $i$-th employee should get a salary from $l_i$ to $r_i$ dollars. You have to distribute salaries in such a way that the median salary is maximum possible.

To find the median of a sequence of odd length, you have to sort it and take the element in the middle position after sorting. For example:  the median of the sequence $[5, 1, 10, 17, 6]$ is $6$,  the median of the sequence $[1, 2, 1]$ is $1$. 

It is guaranteed that you have enough money to pay the minimum salary, i.e $l_1 + l_2 + \dots + l_n \le s$.

Note that you don't have to spend all your $s$ dollars on salaries.

You have to answer $t$ test cases.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of test cases.

The first line of each query contains two integers $n$ and $s$ ($1 \le n < 2 \cdot 10^5$, $1 \le s \le 2 \cdot 10^{14}$) — the number of employees and the amount of money you have. The value $n$ is not divisible by $2$.

The following $n$ lines of each query contain the information about employees. The $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^9$).

It is guaranteed that the sum of all $n$ over all queries does not exceed $2 \cdot 10^5$.

It is also guaranteed that you have enough money to pay the minimum salary to each employee, i. e. $\sum\limits_{i=1}^{n} l_i \le s$.


-----Output-----

For each test case print one integer — the maximum median salary that you can obtain.


-----Example-----
Input
3
3 26
10 12
1 4
10 11
1 1337
1 1000000000
5 26
4 4
2 4
6 8
5 6
2 7

Output
11
1337
6



-----Note-----

In the first test case, you can distribute salaries as follows: $sal_1 = 12, sal_2 = 2, sal_3 = 11$ ($sal_i$ is the salary of the $i$-th employee). Then the median salary is $11$.

In the second test case, you have to pay $1337$ dollars to the only employee.

In the third test case, you can distribute salaries as follows: $sal_1 = 4, sal_2 = 3, sal_3 = 6, sal_4 = 6, sal_5 = 7$. Then the median salary is $6$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t=int(input())

for test in range(t):

    n,s=list(map(int,input().split()))
    LR=[tuple(map(int,input().split())) for i in range(n)]
    LR.sort(reverse=True)

    R=[r for l,r in LR]
    R.sort()

    #print(LR,R)

    MIN=LR[n//2][0]
    MAX=R[n//2]
    
    OK=(n+1)//2

    while MIN!=MAX:
        mid=(MIN+MAX+1)//2
        #print(MIN,MAX,mid)
        count=0
        money=0

        for l,r in LR:

            if count<OK:
                if r>=mid:
                    money+=max(l,mid)
                    count+=1
                else:
                    money+=l

            else:
                money+=l

        if count>=OK and money<=s:
            MIN=mid
        else:
            MAX=mid-1

    print(MIN)
                
            

        

        


import sys
input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T):
    N, S = list(map(int, input().split()))
    X = []
    for __ in range(N):
        l, r = list(map(int, input().split()))
        X.append((l, r))
        
    ok = 1
    ng = 10**9+1

    while ng - ok > 1:
        m = (ok+ng) // 2

        A = []
        B = []
        for i in range(N):
            if X[i][1] >= m:
                A.append(X[i][0])
            else:
                B.append(X[i][0])

        A = sorted(A)[::-1]
        if len(A) > N//2 and sum([max(a, m) for a in A[:N//2+1]]) + sum(A[N//2+1:]) + sum(B) <= S:
            ok = m
        else:
            ng = m

    print(ok)



import sys
readline = sys.stdin.readline

inf = 10**16

def calc(m, L, R):
    N = len(L)
    cl = 0
    cr = 0
    ss = 0
    candi = []
    for i in range(N):
        if L[i] > m:
            cr += 1
            ss += L[i]
        elif R[i] < m:
            cl += 1
            ss += L[i]
        else:
            candi.append(L[i])
    cm = len(candi)
    if cl > N//2:
        return inf
    k = min(cm, N//2 - cl)
    candi.sort()
    ss += sum(candi[:k])
    ss += (cm - k)*m
    
    return ss

T = int(readline())
Ans = [None]*T 
for qu in range(T):
    M, LS = list(map(int, readline().split()))
    L = [None]*M
    R = [None]*M
    for i in range(M):
        L[i], R[i] = list(map(int, readline().split()))
    
    ok = 0
    ng = 10**9+1
    while abs(ok - ng) > 1:
        med = (ok + ng)//2
        if calc(med, L, R) <= LS:
            ok = med
        else:
            ng = med
    Ans[qu] = ok

print('\n'.join(map(str, Ans)))


import sys
def I():
    return sys.stdin.readline().rstrip()

for _ in range( int( I() ) ):
    n, s = list(map( int, I().split() ))
    half = n // 2
    lows = 0
    l, r = [], []
    for _ in range( n ):
        x, y = list(map( int, I().split() ))
        lows += x
        l.append( x )
        r.append( y )
    money = 0
    t = 1
    while t <= 1e9:
        t *= 2
    t //= 2
    while t > 0:
        people = 0
        new_money = money + t
        left = []
        for low, high in zip( l, r ):
            if low <= new_money <= high:
                left.append( new_money - low )
            elif new_money < low:
                people += 1
        left.sort()
        people = half + 1 - people
        if people <= 0 or len( left ) >= people and lows + sum( left[:people] ) <= s:
            money += t
        t //= 2
    print( money )


import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, s = list(map(int, input().split()))
    human = []
    x = n//2 + 1
    for _ in range(n):
        human.append(list(map(int, input().split())))

    human.sort(reverse = True)
    remain = s
    for i in range(n):
        remain -= human[i][0]

    right = 10**9+1
    left = 0
    while right - left > 1:
        mid = left + (right-left)//2
        count = 0
        money = remain
        for i in range(n):
            if human[i][1] < mid:
                continue
            elif human[i][0] >= mid:
                count += 1
                continue
            else:
                if money >= mid - human[i][0]:
                    money -= mid - human[i][0]
                    count += 1
                else:
                    break
        if count >= x:
            left = mid
        else:
            right = mid
    print(left)


def main():
    from array import array
    import sys
    input1 = sys.stdin.readline
    for _ in range(int(input1())):
        n, s = list(map(int, input1().split()))
        n1 = (n + 1) // 2
        z = array('i', (0,))
        ls = z * n
        rs = z * n
        for i in range(n):
            ls[i], rs[i] = list(map(int, input1().split()))
        for l_ in ls:
            s -= l_
        lbs, rbs = 1, 1000000001
        while lbs + 1 < rbs:
            m = (lbs + rbs) // 2
            st = sorted((min(l_, m) for (l_, r) in zip(ls, rs) if r >= m), reverse=True)
            if len(st) >= n1 and m * n1 <= s + sum(st[:n1]):
                lbs = m
            else:
                rbs = m
        sys.stdout.write(f'{lbs}\n')


main()


from sys import stdin
input = stdin.readline
q = int(input())
for rwre in range(q):
	n, s = list(map(int,input().split()))
	przed = [list(map(int,input().split())) for i in range(n)]
	przed.sort()
	przed.reverse()
	l = 1
	p = 10 ** 9
	while abs(p - l) > 0:
		mozna = 1
		sr = (p + l + 1) // 2
		#try to make median >= sr
		duze = [przed[i] for i in range(n) if przed[i][1] >= sr ]
		male = [przed[i] for i in range(n) if przed[i][1] < sr ]
		if len(duze) <= n // 2:
			mozna = 0
		else:
			spent = 0
			dudes = 0
			for i in range(n//2 + 1):
				spent += max(sr, duze[i][0])
			dudes = n//2 + 1
			duze = duze[(n//2+1):]
			for du in duze:
				spent += du[0]
			for ma in male:
				spent += ma[0]
			if spent > s:
				mozna = 0
		if mozna == 1:
			l = sr
		else:
			p = sr - 1
	print((p+l)//2)
						
					
				


import sys
input = sys.stdin.readline
import heapq
sys.setrecursionlimit(100000)
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))

def solve():
    ls, rs = [], []
    n, money = getList()
    sals = []
    for _ in range(n):
        a, b = getList()
        sals.append((a, b))

    # ls.sort()
    # rs.sort()
    ans_mx = 10**10
    ans_mn = 0
    while(ans_mx - ans_mn > 1):
        # print(ans_mx, ans_mn)
        tmp = 0
        heap = []
        mid = (ans_mn + ans_mx) // 2
        for sal in sals:
            if sal[1] < mid:
                tmp += sal[0]
            else:
                heapq.heappush(heap, (-sal[0], -sal[1]))

        # print(len(heap))
        if len(heap) < (n + 1) // 2:
            ans_mx = mid
            continue

        high = 0
        tgt = n // 2
        # print(heap)
        while(heap):
            sal_cur = heapq.heappop(heap)
            if high <= tgt:
                tmp += max(mid, -sal_cur[0])
                high += 1
            else:
                tmp += -sal_cur[0]

        if tmp <= money:
            ans_mn = mid

        else:
            ans_mx = mid
        # print(tmp)

# ================================
#     print(ans_mx, ans_mn)
    tmp = 0
    heap = []
    mid = ans_mx
    # print("mid", mid)
    for sal in sals:
        if sal[1] < mid:
            tmp += sal[0]
        else:
            heapq.heappush(heap, (-sal[0], -sal[1]))

    if len(heap) < (n + 1) // 2:
        print(ans_mn)
        return

    high = 0
    tgt = n // 2
    # print(heap)
    while (heap):
        sal_cur = heapq.heappop(heap)
        # print(sal_cur)
        if high <= tgt:
            tmp += max(mid, -sal_cur[0])
            high += 1
        else:
            tmp += -sal_cur[0]
        # print(tmp)
    if tmp <= money:
        print(mid)
        return

    else:
        print(ans_mn)
        return
    # print(tmp)


def main():
    t = getN()
    for times in range(t):
        solve()


def __starting_point():
    main()

"""
1
3 26
10 12
1 4
10 11

1
1 100
1 1

1
3 6
1 1000
2 1000
3 1000


1
9 100
2 4
3 5
8 100
25 100
2 39
1 2
23 40
1 20
2 10
"""
__starting_point()

import sys
input1 = sys.stdin.readline

def solve():
    n, s = [int(i) for i in input1().split()]
    empl = []
    for i in range(n):
        empl.append([int(j) for j in input1().split()])
    empl.sort(reverse = True)
    lg = 0
    rg = 10 ** 9 + 1
    while rg - lg > 1:
        mg = (rg + lg) // 2
        need = (n + 1) // 2
        money = s
        for i in range(n):
            li = empl[i][0]
            ri = empl[i][1]
            if ri >= mg and need > 0:
                money -= max(mg, li)
                need -= 1
            else:
                money -= li
        if need == 0 and money >= 0:
            check = True
        else:
            check = False
        if check:
            lg = mg
        else:
            rg = mg
    print(lg)

t = int(input1())
while t > 0:
    empl = []
    solve()
    t -= 1

import sys
input = sys.stdin.readline
t=int(input())
while t>0:
    t-=1
    n,ss=map(int,input().split())
    lr=[]
    sl=0
    for i in range(n):
        l,r=map(int,input().split())
        sl+=l
        lr.append([l,r])
        
    l=0
    r=10**9+1
    while r-l>1:
        mid=(r+l)//2
        s=[]
        for i in range(n):
            if mid<=lr[i][1]:
                s.append(max(-lr[i][0],-mid))
                
        if len(s)<n//2+1:
            r=mid
            continue
        s.sort()
        sumi=sl+(n//2+1)*mid+sum(s[:n//2+1])
       
        if sumi>ss:
            r=mid
        else:
            l=mid
        #print(r,l)
        #print(r,l,sumi,ss)    
    print(l)    

def check(x, s, a, n):
    num   = (n+1)  // 2
    cur   = 0
    sum_  = 0
    
    for i in range(n-1, -1, -1):
        l, r   = a[i]
        
        if cur == num:
            break
        
        if l >= x:
            cur  += 1
            
        elif l <= x and x <= r:
            cur  += 1
            sum_ += x - l
    
    if cur == num and sum_ <= s:
        return True
    
    return False

q = int(input())

ans = []
for _ in range(q):
    n, s = list(map(int, input().split()))
    a    = [list(map(int, input().split())) for _ in range(n)]
    a    = sorted(a, key = lambda x: x[0])

    s    = s - sum([l for l, r in a]) 
    l, u = a[n // 2][0], 1000000000

    while u - l > 1:
        md = (u+l) // 2
    
        if check(md, s, a, n) == True:
            l = md
        else:
            u = md
        
    ans.append(str(l))       

print('\n'.join([x for x in ans]))    
#3
#3 26
#10 12
#1 4
#10 11
#1 1337
#1 1000000000
#5 26
#4 4
#2 4
#6 8
#5 6
#2 7


import sys
input = sys.stdin.readline
 
  
def solve(mid):
    ans = 0
    cnt = 0
    tmp = []
    for i in range(n):
        l, r = info[i]
        if r < mid:
            ans += l
        elif mid < l:
            ans += l
            cnt += 1
        else:
            tmp.append(l)
    tmp.sort(reverse = True)
    nokori = (n+1) // 2 - cnt
    for i in tmp:
        if nokori > 0:
            ans += mid
            nokori -= 1
        else:
            ans += i
    if ans <= s and nokori <= 0:
        return True
    else:
        return False

q = int(input())
for _ in range(q):
    n, s = map(int, input().split())
    info = [list(map(int, input().split())) for i in range(n)]
    ok = 0
    ng = s + 1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    print(ok)

import sys
input = sys.stdin.readline
 
  
def solve(mid):
    ans = 0
    cnt = 0
    tmp = []
    for i in range(n):
        l, r = info[i]
        if r < mid:
            ans += l
        elif mid < l:
            ans += l
            cnt += 1
        else:
            tmp.append(l)
    tmp.sort(reverse = True)
    nokori = (n+1) // 2 - cnt
    for i in tmp:
        if nokori > 0:
            ans += mid
            nokori -= 1
        else:
            ans += i
    if ans <= s and nokori <= 0:
        return True
    else:
        return False

q = int(input())
ans = [0]*q
for qi in range(q):
    n, s = map(int, input().split())
    info = [list(map(int, input().split())) for i in range(n)]
    ok = 0
    ng = s + 1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    ans[qi] = ok
print('\n'.join(map(str, ans)))

import sys
input = sys.stdin.readline
 
  
def solve(mid):
    ans = 0
    cnt = 0
    tmp = []
    for i in range(n):
        if info[i][1] < mid:
            ans += info[i][0]
        elif mid < info[i][0]:
            ans += info[i][0]
            cnt += 1
        else:
            tmp.append(info[i][0])
    tmp.sort(reverse = True)
    nokori = (n+1) // 2 - cnt
    for i in tmp:
        if nokori > 0:
            ans += mid
            nokori -= 1
        else:
            ans += i
    if ans <= s and nokori <= 0:
        return True
    else:
        return False

q = int(input())
ans = [0]*q
for qi in range(q):
    n, s = map(int, input().split())
    info = [list(map(int, input().split())) for i in range(n)]
    ok = 0
    ng = s + 1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    ans[qi] = ok
print('\n'.join(map(str, ans)))

import sys

input1 = sys.stdin.readline


def solve():
    n, s = [int(i) for i in input1().split()]
    empl = [[] for i in range(n)]
    for i in range(n):
        empl[i] = [int(j) for j in input1().split()]
    empl.sort(reverse=True)
    lg = 0
    rg = 10 ** 9 + 1
    while rg - lg > 1:
        mg = (rg + lg) // 2
        need = (n + 1) // 2
        money = s
        for [li, ri] in empl:
            if ri >= mg and need > 0:
                money -= max(mg, li)
                need -= 1
            else:
                money -= li
        if need == 0 and money >= 0:
            check = True
        else:
            check = False
        if check:
            lg = mg
        else:
            rg = mg
    print(lg)

t = int(input1())
while t > 0:
    empl = []
    solve()
    t -= 1

from sys import stdin, stdout 
def fun1(n,m,l,s):
    cl=0
    cr=0
    cm=0
    for i in range(n):
        if l[i][1]<m:
            s-=l[i][0]
            cl+=1
        elif l[i][0]>m:
            s-=l[i][0]
            cr+=1
        else:
            cm+=1
            if (cm+cr)<=1+n//2:
                s-=m
            else:
                s-=l[i][0]
        if (s<0 or cr>n//2 or cl>n//2):
            return(0)
    return(1)

def search(n,low,high,l,su):
    l1=l[::-1]
    while(low<high):
        mid=(low+high)//2
        if fun1(n,mid,l1,su):
            low=mid+1
        else:
            high=mid
    if fun1(n,low,l1,su):
        return(low)
    return(low-1)


def main():
    for _ in range(int(stdin.readline())):
        n,su=[int(x) for x in stdin.readline().split()]
        l=[[-1,-1] for i in range(n)]
        l2=[-1 for i in range(n)]
        for i in range(n):
            inp=[int(j) for j in stdin.readline().split()]
            l[i]=inp
            l2[i]=inp[0]
        l.sort()
        low=int(l[n//2][0])
        print(search(n,low,(10**9)+1,l,su))

def __starting_point(): 
    main()  

__starting_point()

def check(mid):
    x=[]
    y=[]
    z=[]
    for i in it:
        if i[1]<mid:
            x.append(i)
        elif i[0]>=mid:
            y.append(i)
        else:
            z.append(i)
    co=sum([i[0] for i in x])
    co+=sum([i[0] for i in y])
    ll=len(y)
    m=0

   #if len(z)==0:
    #    return False
    ne=max(0,(n+1)//2-ll)
    if ne>len(z):
        return False
    j=0
    for i in z:
        if j<len(z)-ne:
            co+=i[0]
        else:
            co+=mid
        j+=1
    
    return co<=s
   
import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n,s=list(map(int,input().split()))
    it=[]
    for i in range(n):
        it.append(list(map(int,input().split())))
    it.sort()
    l=1
    r=max(it,key=lambda x:x[1])[1]+1
    while abs(l-r)>=2:
        mid=(l+r)//2
        st=check(mid)
        if st:
            l=mid
        else:
            r=mid
    ma=l
    for i in range(l,r+1):
        st=check(i)
        if st:
            ma=max(ma,i)
    print(ma)


def check(x, s, a, n):
    num = (n+1) // 2
    cur = 0
    sum_ = 0

    for i in range(n-1, -1, -1):
        l, r = a[i]

        if cur == num:
            break

        if l >= x:
            cur += 1

        elif l <= x and x <= r:
            cur += 1
            sum_ += x - l

    if cur == num and sum_ <= s:
        return True

    return False


q = int(input())

ans = []
for _ in range(q):
    n, s = list(map(int, input().split()))
    a = [list(map(int, input().split())) for _ in range(n)]
    a = sorted(a, key=lambda x: x[0])

    s = s - sum([l for l, r in a])
    l, u = a[n // 2][0], 1000000000

    while u - l > 1:
        md = (u+l) // 2

        if check(md, s, a, n) == True:
            l = md
        else:
            u = md

    ans.append(str(l))

print('\n'.join([x for x in ans]))


3

import array
import math
import os
import sys


def main():
    T = read_int()
    for _ in range(T):
        N, S = read_ints()
        A = [read_ints() for _ in range(N)]
        print(solve(N, S, A))


def solve(N, S, A):
    minv = [l for l, r in A]
    minv.sort()

    half = N // 2

    def feasible(target):
        low = []
        high = []
        mid = []
        for p in A:
            l, r = p
            if target < l:
                high.append(p)
            elif r < target:
                low.append(p)
            else:
                mid.append(p)

        if len(low) >= half + 1 or len(high) >= half + 1:
            return False

        tsum = 0
        for l, r in low:
            tsum += l
        for l, r in high:
            tsum += l

        mid.sort()
        midi = half - len(low)
        for i in range(midi):
            l, r = mid[i]
            tsum += l
        tsum += target * (len(mid) - midi)

        return tsum <= S

    lb = minv[half]
    ub = 10 ** 9 + 1
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if feasible(mid):
            lb = mid
        else:
            ub = mid
    return lb


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def __starting_point():
    main()

__starting_point()

import sys
import math
from collections import defaultdict
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : list(map(int, input().split()))
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}".format(i) + sep)
INF = float('inf')
MOD = int(1e9 + 7)

for t in range(int(input())):
  n, x= read()
  lr = sorted([list(read()) for i in range(n)], reverse = True)

  s = 0
  e = 1<<32
  while s <= e:
    m = (s + e) // 2
    money = 0
    a, b, c = [], [], [] 

    for l, r in lr:
      if l > m:
        c.append((l, r))
        money += l 
      elif r < m:
        a.append((l, r))
        money += l 
      else:
        b.append((l, r))
    
    if money > x or len(a) >= n//2 + 1:
      e = m - 1 
      continue
    
    need = n//2 + 1 - len(c)
    cnt = 0
    #print(money, a,b,c,m, sep="\n")
    for l, r in b:
      
      #print(money, cnt, need, l, r)
      if cnt < need:
        money += m  
        cnt += 1
      else:
        money += l
    if money <= x:
      s = m + 1 
    else:
      e = m - 1
  
  print(e)

    



       




    


import sys
import math
from collections import defaultdict
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : list(map(int, input().split()))
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}".format(i) + sep)
INF = float('inf')
MOD = int(1e9 + 7)

for t in range(int(input())):
  n, x= read()
  lr = sorted([list(read()) for i in range(n)], reverse = True)

  s = 0
  e = 1<<32
  while s <= e:
    m = (s + e) // 2
    money = 0
    a, b, c = [], [], [] 

    for l, r in lr:
      if l > m:
        c.append((l, r))
        money += l 
      elif r < m:
        a.append((l, r))
        money += l 
      else:
        b.append((l, r))
    
    if money > x or len(a) >= n//2 + 1:
      e = m - 1 
      continue
    
    need = n//2 + 1 - len(c)
    cnt = 0
    #print(money, a,b,c,m, sep="\n")
    for l, r in b:
      
      #print(money, cnt, need, l, r)
      if cnt < need:
        money += m  
        cnt += 1
      else:
        money += l
    if money <= x:
      s = m + 1 
    else:
      e = m - 1
  
  write(e)

    



       




    


import sys
import math
from collections import defaultdict
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : list(map(int, input().split()))
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}".format(i) + sep)
INF = float('inf')
MOD = int(1e9 + 7)

for t in range(int(input())):
  n, x= read()
  lr = sorted([list(read()) for i in range(n)], reverse = True)

  s = 0
  e = 1<<32
  while s <= e:
    m = (s + e) // 2
    money = 0
    a, b, c = 0, [], 0 

    for l, r in lr:
      if l > m:
        c += 1
        money += l 
      elif r < m:
        a += 1
        money += l 
      else:
        b.append((l, r))
    
    if money > x or a >= n//2 + 1:
      e = m - 1 
      continue
    
    need = n//2 + 1 - c
    cnt = 0
    #print(money, a,b,c,m, sep="\n")
    for l, r in b:
      
      #print(money, cnt, need, l, r)
      if cnt < need:
        money += m  
        cnt += 1
      else:
        money += l
    if money <= x:
      s = m + 1 
    else:
      e = m - 1
  
  write(e)