Harryxun/stf_run huggingface dataset:
from sys
rl=sys.stdin.readline

def main():
    n,k=map(int,rl.strip().split())
    ints=[list(map(int,rl.strip().split())) for _ in range(n)]
    ints.sort(key=lambda e:e[0])
    s=0
    for e in ints:
        s+=e[1]
        if s<=k:
            print(e[0])
            break

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
rl=sys.stdin.readline

def main():
    n,k=map(int,rl().strip().split())
    ints=[list(map(int,rl().strip().split())) for _ in range(n)]
    ints.sort(key=lambda e:e[0])
    s=0
    for e in ints:
        s+=e[1]
        if s>=k:
            print(e[0])
            break

if __name__=='__main__':
    main()
s = list(input())
if s == "BBB":
print("NO")

elif s == "AAA":
print("NO")

else:
print("YES")

### FIXED CODE ###

s = input()
if s == "BBB":
	print("No")
elif s == "AAA":
	print("No")
else:
	print("Yes")
input_str = input()

translate_num = (int(input_str))**2

print(translate_num\n)

### FIXED CODE ###

input_str = input()

translate_num = (int(input_str))**3

print(translate_num)
from math import atan, pi

a,b,v = map(int, input().split())
if v*2 < a*a*b:
  e= v*2/(a*b)
  theta = atan(e/b)
else:
  e = 2*(a*b - v/a)/a
  theta = atan(a/e)
theta *= 180/pi
print(90.0 - theta)

### FIXED CODE ###

from math import atan, pi

a,b,v = map(int, input().split())
if v == a*a*b:
  theta = pi/2
elif v*2 < a*a*b:
  e= v*2/(a*b)
  theta = atan(e/b)
else:
  e = 2*(a*b - v/a)/a
  theta = atan(a/e)
theta *= 180/pi
print(90.0 - theta)
sa = [s for s in input()]
sb = [s fir s in input()]
sc = [s for s in input()]

next_turn = "a"
flag = True

while flag:
    if next_turn == "a":
        if len(sa) == 0:
            print("A")
            flag = False
        else:
            next_turn = sa.pop(0)
    elif next_tunr == "b":
        if len(sb) == 0:
            print("B")
            flag = false
        else:
            next_turn = sb.pop(0)
    elif next_turn == "c":
        if len(sc) ==0:
            print("C")
            flag = False
        else:
            next_turn = sc.pop(0)
        



### FIXED CODE ###

sa = list(input())
sb = list(input())
sc = list(input())

turn = "a"

while True:
    if turn == "a":
        if len(sa) != 0:
            turn = sa.pop(0)
        else:
            print("A")
            exit()
    elif turn == "b":
        if len(sb) != 0:
            turn = sb.pop(0)
        else:
            print("B")
            exit()
    else:
        if len(sc) != 0:
            turn = sc.pop(0)
        else:
            print("C")
            exit()
n,d=map(int,input().split())
def f(r):return r[0]**2+r[1]**2
print(sum(f(list(map(int,input().split()))) for _ in range(n))

### FIXED CODE ###

n,d=map(int,input().split())
s=0
for _ in range(n):
  x,y=map(int,input().split())
  if x**2+y**2<=d**2:s+=1
print(s)
a = input()
b = input()
for i in range(0,3):
  if a[i] == 'S':
    a[i] = '1'
  elif a[i] == 'C':
    a[i] = '2'
  else:
    a[i] = '3'
for j in range(0,3):
  if b[j] == 'S':
    b[j] = '1'
  elif b[j] == 'C':
    b[j] = '2'
  else:
    b[j] = '3'
out = 0
for k in range(0,3):
  if int(a[k]-b[k]) == 0:
    out = out + 1
print(out)

### FIXED CODE ###

a = input()
b = input()
out=0
for i in range(0,3):
  if a[i] ==b[i]:
    out =out+1
print(out)
import time
MOD =  1000000007
MOD2 = 1000000005

facs = [1 for _ in range(50001)]
inv = [1 for _ in range(50001)]


for i in range(1, 50001):
	facs[i] = (facs[i-1] * i) % MOD

for i in range(1, 50001):
	inv[i] = pow(facs[i], MOD2, MOD)


def get_facs(x):
	return facs[x]


def get_inv(x):
	return inv[x]

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	r = (get_facs(n)*get_inv(k)) % MOD
	r = (r*get_inv(n-k)) % MOD
	print(n, k, r)
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		s = ((choose(i, K-1) - choose(N-1-i, K-1)) * x)
		score = int((score+s))

	return int(score%MOD)
	
	
print(main())


### FIXED CODE ###

import time
MOD =  1000000007
MOD2 = 1000000005
MAX = 100001

facs = [1 for _ in range(MAX)]
inv = [1 for _ in range(MAX)]


for i in range(1, MAX):
	facs[i] = (facs[i-1] * i) % MOD

for i in range(1, MAX):
	inv[i] = pow(facs[i], MOD2, MOD)


def get_facs(x):
	return facs[x]


def get_inv(x):
	return inv[x]

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	r = (get_facs(n)*get_inv(k)) % MOD
	r = (r*get_inv(n-k)) % MOD
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return abs(numbers[0] - numbers[-1])

	score = 0
	for i, x in enumerate(numbers):
		score += ((choose(i, K-1) - choose(N-1-i, K-1)) * x)

	return score%MOD
	
	
print(main())
import fractions

s = input().split()
n, k = int(s[0]), int(s[1])

ans = int(fractions.log(n, k) + 1.0)
print(ans)

### FIXED CODE ###

import math
 
s = input().split()
n, k = int(s[0]), int(s[1])
 
ans = int(math.log(n, k) + 1.0)
print(ans)
new_a = []

for k in range(n):
    a.append(str(input()))

for k in range(n):
    new_a.append( ''.join(list(sorted(a[k]))))

new_a.sort()

b = 0

for k in range(n-1):
    for m in range(k+1, n):
        if(new_a[k] == new_a[m]):
            b = b +1

print(b)


### FIXED CODE ###

import math
n = int(input())
list_voc = [str(input()) for _ in range(n)]
list_mo = []
for i, s in enumerate(list_voc):
    list_n = list(s)
    list_n.sort()
    list_n = ''.join(list_n)
    list_mo.append(list_n)

ans = {}
for s in list_mo:
    if s in ans:
        ans[s] += 1
    else:
        ans[s] = 1


ans_val = []

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


for s in ans:
    if ans[s] != 1:
        ans_val.append(cmb(ans[s], 2))


print(sum(ans_val))
# -*- coding: utf-8 -*-

asset = []

for b in range(1,100):
    for p in range(2,100):
        tmp = pow(b, p)
        if tmp < 1001:
            if tmp not in asset:
                asset.append(tmp)

#print(asset)

x = int(input())

new_asset = []
for i in range(len(asset)):
    if asset[i] < x:
        new_asset.append(asset[i])

print(max(new_asset))

### FIXED CODE ###

# -*- coding: utf-8 -*-

x = int(input())

kk = [1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000]

ans = [i for i in kk if (i <= x)]
print(ans[-1])
n=int(input())
for i in range(9):
    for j in range(9):
        k = (i+1)*(j+1)
        if n%k==0:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###


a,b=map(int,input().split())
if a<10 and b<10:
    print(a*b)
else:
    print('-1')
n = int(input())
v_list = list(map(int, input().split()))
while len(v_list) != 1:
    sort(v_list)
    a = v_list.pop()
    b = v_list.pop()
    v_list.append((a + b) / 2)
print(v_list[0])

### FIXED CODE ###

N = int(input())
v = list(map(int, input().split()))
 
 
v.sort(reverse = True)
 
for i in range(N-1):
    a = v.pop()
    b = v.pop()
    v.append((a+b)/2)
    v.sort(reverse = True)
 
print(v[0])
n = int(input())
c = input()
r=0
w=0
p=0
count = 0
for i in range(len(c)):
    if c[i]=="R":
        r+=1
    else:
        w+=1
white = []

for i in range(len(c)):
    if c[i]=="R":
        r-=1
        
    else:
        white.append(r)
    if r==0:
        break
if len(white)==0:
    print(0)
if white[0]==0:
    print(0)
else:
    for i in range(len(white)):
        if white[-i-1]>=len(white)-i:
            print(len(white)-i)
            break
print(white)

### FIXED CODE ###

n = int(input())
c = input()
r=0
w=0
p=0
count = 0
for i in range(len(c)):
    if c[i]=="R":
        r+=1
    else:
        w+=1
white = []

for i in range(len(c)):
    if c[i]=="R":
        r-=1
        
    else:
        white.append(r)
    if r==0:
        break
if len(white)==0:
    print(0)
elif white[0]==0:
    print(0)
else:
    for i in range(len(white)):
        if white[-i-1]>=len(white)-i:
            print(len(white)-i)
            break
SR=S+[S[0]]
cnt=0
for i in range(len(S)-1):
  if SR[i]==SR[i+1]==SR[i+2]:
    SR[i+1]=0
    cnt+=1

for i in range(len(S)):
  if SR[i]==SR[i+1]:
    SR[i]=0
    cnt+=1
    
if SR[-2]==0 and S[-1]!=S[-2]:
  ans = cnt*K-1
else:
  ans = cnt*K
print(ans)

### FIXED CODE ###

s=list(input())
k=int(input())

if len(set(s))==1:
  print((len(s)*k)//2)
  exit()

t=[1]
for i in range(1,len(s)):
  if s[i-1]==s[i]:
    t[-1]+=1
  else:
    t.append(1)
    
ans=0
for i in t:
  ans+=(i//2)*k

if s[0]==s[-1]:
  ans+= ((t[0]+t[-1])//2 - (t[0]//2+t[-1]//2))*(k-1)

print(ans)
a, b, c = map(int, input().split())
if a < b < c:
 print "Yes"
elif:
 print "No"

### FIXED CODE ###

a, b, c = map(int, raw_input().split())
if a < b and b < c:
 print "Yes"
else:
 print "No"
L = []
while True:
    l = list(map(int, input().split()))
    if l:
        L.append(l)
    else:
        break

N = L[0][0]
K = L[0][1]

Num = list(range(1,N+1,1))

new_L = L[2::2]

new_LL = sum(new_L,[])
for n in new_LL:
    if n in Num:
        Num.remove(n)

print(len(Num))


### FIXED CODE ###

import sys

L = []
"""
while True:
    l = input()
    if l == "":
        break
    else:
        L.append(list(map(int,l.split())))
        print(L)
"""
N,K = list(map(int,input().split()))

#print(N,K)

for a in range(2 * K):
    n = list(map(int,input().split()))
    L.append(n)

#print("End",L)

Num = list(range(1, N + 1, 1))
#print(Num)
new_L = L[1::2]
#print(new_L)

new_LL = sum(new_L, [])
for n in new_LL:
    if n in Num:
        Num.remove(n)

print(len(Num))
n,m = map(int,input().split(" "))

roads = []
for i in range(m):
    roads.append(input())

def count_road(n,m,str_roads):
    city_roads_count = [0] * m
    for road in str_roads:
        a,b = map(int,input().split(" "))
        city_roads_count[a-1] += 1
        city_road_count[b-1] += 1
    return city_roads_count


for road_cout in roads_count:
    print(road)

### FIXED CODE ###

n,m = map(int,input().split(" "))

city_road_count = [0] * n
for i in range(m):
      a,b = map(int,input().split(" "))
      city_road_count[a-1] += 1
      city_road_count[b-1] += 1
      
for c in city_road_count:
      print(c)
#include <iostream>
#include <algorithm>
#include <vector>


int main()
{
    long long  n,m,k; std::cin >> n >> m >> k;
    // long long  a[n+1], b[m+1];
    std::vector<long long>  a{n+1}, b{m+1};
    a[0]=0; b[0]=0;
    for (int i=1;i<n+1;i++)
        std::cin >> a[i];
    for (int i=1; i<m+1; i++)
        std::cin >> b[i];
    
    for (int i=1; i<n+1; i++)
        a[i]+=a[i-1];
    for (int i=1; i<m+1; i++)
        b[i]+=b[i-1];

    int ans=0, r=m;
    for (int i=0; i<n+1; i++)
    {
        if(a[i]>k) break;
        while (a[i]+b[r]>k)
            r--;
        ans = std::max({ans, i+r});
    }
    
    std::cout << ans;

    return 0;
}

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m,k = map(int, readline().split())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))

sa = [0]*(n+1)
sb = [0]*(m+1)

for i in range(n):
    sa[i+1] = sa[i]+a[i]
for i in range(m):
    sb[i+1] = sb[i]+b[i]

isb=m
ans = 0
for isa in range(n+1):
    if sa[isa]>k:
        break
    #while isb>0 and sa[isa]+sb[isb]>k:
    while sa[isa]+sb[isb]>k:
        isb-=1
    ans = max(ans, isa+isb)
    
print(ans)
n = int(input())
b = list(map(int, input().split()))
ans = b[0]
for i in range(len(b)-1):
  ans.append(min(b[i], b[i+1]))
  ans += b[-1]
print(ans)


### FIXED CODE ###

n=int(input())
print(n**3)
import math
a, b, x = map(int, input().split())


if x <= a**2 * b / 2:
    print(math.degrees(math.atan(a * b**2 / 2 * x)))
else:
    print(math.degrees(math.atan(2(a**2 * b - x) / a**3)))


### FIXED CODE ###

import math
a, b, x = map(float, input().split())


if x <= (a**2 * b) / 2:
    print(math.degrees(math.atan(a * b**2 / (2 * x))))
else:
    print(math.degrees(math.atan(2 * (a**2 * b - x) / a**3)))
def main():
    N = int(input())
    A = list(map(int, input().split()))

    if N == 2:
        print(max(A[0]+A[1], (-A[0])+(-A[1])))
        return

    a_sum, a1, a2 = 0, A[0], A[1]
    b_sum, b1, b2 = 0, -A[0], -A[1]

    for i in range(2, N):

        if (a_sum + a1 + a2 + A[i]) > (b_sum + b1 + b2 + A[i]):
            new_a_sum = a_sum + a1
            new_a1 = a2
            new_a2 = A[i]
        else:
            new_a_sum = b_sum + b1
            new_a1 = b2
            new_a2 = A[i]

        if (a_sum + a1 - a2 - A[i]) > (b_sum + b1 - b2 - A[i]):
            new_b_sum = a_sum + a1
            new_b1 = -a2
            new_b2 = -A[i]
        else:
            new_b_sum = b_sum + b1
            new_b1 = -b2
            new_b2 = -A[i]

        a_sum, a1, a2 = new_a_sum, new_a1, new_a2
        b_sum, b1, b2 = new_b_sum, new_b1, new_b2

    print(max(a_sum+a1+a2, b_sum+b1+b2))

main()

### FIXED CODE ###

a, b, t = map(int, input().split())

print((t // a)*b)
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
a0,a1= np.unique(a,return_counts=True)
suma=np.sum(a)
a2=np.array([0]*100000)
for j in range(a0.size):
  a2[a0[j]]=a1[j]
#print(suma)
#print(a0)
#print(a1)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  sumb=a2[b]
  a2[b]=0
  a2[c]+=sumb
  sumc=sumb*(c-b)
  suma+=sumc
  print(suma)

### FIXED CODE ###

import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
a0,a1= np.unique(a,return_counts=True)
suma=np.sum(a)
a2=np.array([0]*100001)
for j in range(a0.size):
  a2[a0[j]]=a1[j]
#print(suma)
#print(a0)
#print(a1)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  sumb=a2[b]
  a2[b]=0
  a2[c]+=sumb
  sumc=sumb*(c-b)
  suma+=sumc
  print(suma)
x = input().split()
a = float(x[0])
b = float(x[1]))
ans = int(a*b)
print(ans)

### FIXED CODE ###

from decimal import *
getcontext().prec = 18
x = input().split()

aa = Decimal(x[0])*Decimal(x[1])

print(int(aa))
n = int(input())
commands = [input().split() for _ in range(n)]

l = []
for com in commands:
    print(l)
    if com[0]=='insert':
        l.insert(0, com[1])
    elif com[0]=='delete':
        try:
            l.remove(com[1])
    elif com[0]=='deleteFirst':
        l.pop(0)
    elif com[0]=='deleteLast':
        l.pop()
s = ' '.join(l)
print(s)


### FIXED CODE ###

from collections import deque

n = int(input())
commands = [input() for _ in range(n)] # splitとかしてると間に合わない

l = deque()
for com in commands:
    if com[0]=='i':
        l.appendleft(com[7:])
    elif com[6]=='F':
        l.popleft()
    elif com[6]=='L':
        l.pop()
    else:
        try:
            l.remove(com[7:])
        except:
            pass

s = ' '.join(l)
print(s)
a = int(input())
i = 0

while a != 0:
	print("Case " + i + ": " + a)
	i += 1
	a = int(input())


### FIXED CODE ###

a = input()
i = 1

while a != "0":
	print("Case " + str(i) + ": " + a)
	i += 1
	a = input()
N=int(input())
  total=0
  for i in range (1,N+1):
if i%3!=0 and i%5=0
  total+=i
  print(total)

### FIXED CODE ###

N = int(input())
total = 0
for i in range(1, N+1):
    if i % 3 != 0 and i % 5 != 0:
        total += i
print(total)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
ans = []

# 負
if len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans.append(-minus.pop())
# 正 or 0
else:
    while len(ans) != k:
        if len(ans) == k-1:
            ans.append(plus_zero.popleft())
        else:
            if len(plus_zero) < 2:
                ans.append(minus.popleft())
                ans.append(minus.popleft())
                continue
            elif len(minus) < 2:
                ans.append(plus_zero.popleft())
                continue
            else:
                if (plus_zero[0] * plus_zero[1]) >= (minus[0] * minus[1]):
                    ans.append(plus_zero.popleft())
                else:
                    ans.append(minus.popleft())
                    ans.append(minus.popleft())
                continue

import functools
print(functools.reduce(lambda x, y: x * y, ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
ans_lst = []
# 境界条件: k == n
if k == n:
    ans_lst.extend(a)
# 負
elif len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans_lst.append(-minus.pop())
# 正 or 0
else:
    while len(ans_lst) != k:
        if len(ans_lst) == k-1:
            ans_lst.append(plus_zero.popleft())
        else:
            if len(plus_zero) == 0:
                ans_lst.append(minus.popleft())
                ans_lst.append(minus.popleft())
                continue
            if len(plus_zero) == 1:
                if (k - len(ans_lst)) % 2 == 0:
                    ans_lst.append(minus.popleft())
                    ans_lst.append(minus.popleft())
                else:
                    ans_lst.append(plus_zero.popleft())
                continue
            if len(minus) < 2:
                ans_lst.append(plus_zero.popleft())
                continue
            if len(plus_zero) >= 2 and len(minus) >= 2:
                if (plus_zero[0] * plus_zero[1]) >= (minus[0] * minus[1]):
                    ans_lst.append(plus_zero.popleft())
                else:
                    ans_lst.append(minus.popleft())
                    ans_lst.append(minus.popleft())
                continue
# functools.reduceはTLEをくらう場合があるので気をつける
ans = 1
for i in ans_lst:
    ans = (ans * i) % MOD
print(ans)
import sys
X = int(input())
MAX = 10**9
M = [1, -1]
i = 1
while i**5 < MAX:
  i += 1
  M.append(i**5)
  M.append(-i**5)
  
for i in M:
  for j in M:
    if i - j == X:
      if j < 0:
        print(int(i**(1/5)), -int((-j)**(1/5)))
      else:
        print(int(i**(1/5)), int(j**(1/5)))
      sys.exit(0)


### FIXED CODE ###

import sys
X = int(input())
MOD = 10**9+7
M = [i*m for i in range(0, 10**4) for m in [-1, 1]]
for i in range(0, 10**4):
  for j in M:
    if i == j:
      break
    if X%(i-j)==0:
      if i**5-j**5==X:
        print(i, j)
        sys.exit(0)
N=int(input())
flag='Yes'
p,q,r=0,0,0
for _ in range(N):
  t,x,y=map(int,input().split())
  a=x+y-p-q
  e=t-r
  if a<=e:
    if (e-a)%2!=0:
      flag='No'
      break
  else:
    flag='No'
    break
  p=x
  q=y
  r=t
print(flag)N=int(input())
flag='Yes'
p,q,r=0,0,0
for _ in range(N):
  t,x,y=map(int,input().split())
  a=x+y-p-q
  e=t-r
  if a<=e:
    if (e-a)%2!=0:
      flag='No'
      break
  else:
    flag='No'
    break
  p=x
  q=y
  r=t
print(flag)

### FIXED CODE ###

N=int(input())
flag='Yes'
p,q,r=0,0,0
for _ in range(N):
  t,x,y=map(int,input().split())
  a=abs(x-p)+abs(y-q)
  e=t-r
  if a<=e:
    if (e-a)%2!=0:
      flag='No'
      break
  else:
    flag='No'
    break
  p,q,r=x,y,t
print(flag)
def popcount(n):
	res=0
	while n > 0:
		res += n%2;
		n /= 2
	return res
n=0
def init_seg(_n):
	n=1
	while(n < _n) n *= 2

data=[0]*n
datb=[0]*n

def add(a,b,x,k,l,r):
	if a <=l and r <= b:
		data[k] += x
	else:
		datb[k] += (min(b,r) - max(a,l))*x
		add(a,b,x,2*k+1,l,(l+r)/2)
		add(a,b,x,2*k+2,(l+r)/2,r)

def sum(a,b,k,l,r):
	if b <=l or r <=a:
		return 0
	elif a <= l and r <= b:
		return data[k] * (r - l) + datb[k]
	else:
		res=(min(b,r) - max(a,l)) * data[k]
		res+=sum(a,b,2*k+1,l,(l+r)/2)
		res+=sum(a,b,2*k+2,(l+r)/2,r)
		return res

init_seg(1e5)
for i in range(n):
	add(i,i+1,0,0,0,n)

N,C=map(int,input().split())
for i in range(N):
	s,t,c=map(int,input().split())
	add(s,t,2**(c-1),0,0,n)

res=0
for i in range(1,1e5):
	prev=sum(i-1,i,0,0,n)
	curr=sum(i,i+1,0,0,n)
	if prev == curr:
		res = max(res, popcount(curr))
	else:
		res = max(res, popcount(curr | prev))

print(res)



### FIXED CODE ###

N,C=map(int,input().split())
f=[[0]*int(1e5) for _ in range(C)]

for i in range(N):
	s,t,c=map(int,input().split())
	f[c-1][s-1:t]=[1]*(t-s+1)

print(max(map(sum,zip(*f))))
N = int(input())
a = [int(i) for i in input().split()]
result = 1
delta = 0
for i in range(1,n) :
    if a[i-1] < a[i]:
        ndelta = 1
    elif a[i-1] > a[i]:
        ndelta = -1
    else:
        ndelta = 0
        
    if delta and ndelta and delta != ndelta:
        result += 1
        delta = 0
    elif not delta:
        delta = ndelta
    
print(result)
    
            

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
result = 1
delta = 0
for i in range(1,N) :
    if a[i-1] < a[i]:
        ndelta = 1
    elif a[i-1] > a[i]:
        ndelta = -1
    else:
        ndelta = 0
        
    if delta and ndelta and delta != ndelta:
        result += 1
        delta = 0
    elif not delta:
        delta = ndelta
    
print(result)
def Main(A,B,C):

  if A == B:
    if C!=A:
      print("Yes",end="")
    else:
      print("No",end="")
  elif A == C:
    if B!=A:
      print("Yes",end="")
    else :
      print("No",end="")
  elif B == C:
    if A!=B :
      print("Yes",end="")
    else:
      print("No",end="")
  else:
    print("No",end="")
A = int(input())
B = int(input())
C = int(input())
Main(A,B,C)


### FIXED CODE ###

def Main(A,B,C):

  if A == B:
    if C!=A:
      print("Yes",end="")
    else:
      print("No",end="")
  elif A == C:
    if B!=A:
      print("Yes",end="")
    else :
      print("No",end="")
  elif B == C:
    if A!=B :
      print("Yes",end="")
    else:
      print("No",end="")
  else:
    print("No",end="")
A,B,C = [int(num) for num in input().split(' ')]
Main(A,B,C)
import numpy as np

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = np.zeros(W+1, dtype=np.int64)

for i, (w, v) in enumerate(items):
  tmp = dp[:-w] + v
  dp[w:] = np.maximum(dp[w:], tmp)
print(dp[W])

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = np.full(10**5+1, 10**18, dtype=np.int64)
dp[0] = 0

for i, (w, v) in enumerate(items):
  tmp = dp[:-v] + w
  dp[v:] = np.minimum(dp[v:], tmp)
print(np.max(np.where(dp <= W)))
S = input()

if S = 'ABC':
  print('ARC')
else:
  print('ABC')

### FIXED CODE ###

S = input()
 
if S == 'ABC':
  print('ARC')
else:
  print('ABC')
if 0 in A:
  print(0)
  exit()

  
ans = 1
A.sort(reverse = True)
for i in range(len(A)):
  ans = ans * A[i] 
  if ans > lim:
    print(-1)
    exit()

if ans > lim:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
lim = 10**18

if 0 in A:
  print(0)
  exit()

  
ans = 1
A.sort(reverse = True)
for i in range(len(A)):
  ans = ans * A[i] 
  if ans > lim:
    print(-1)
    exit()

if ans > lim:
  print(-1)
else:
  print(ans)
N,M = map(int, input().split())
A = []
for X in input().split():
	x = int(X)
	A.append(x)

for x in range(M):
	max = A.index(max(A))
	A[max] = A[max] / 2

sum = 0
for x in range(len(A)):
	sum += int(A[x])

print(sum)


### FIXED CODE ###

import heapq

N,M = map(int, input().split())
A = [-int(n) for n in input().split()]

heapq.heapify(A)
for x in range(M):
	heapq.heappush(A, heapq.heappop(A)/2)
A_int = map(int, A)
print(-sum(A_int))