Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,k=mii()
arr=limii()
aa=[]
for i in range(n):
    arri=arr[i]
    aa.append((arri*(arri+1)//2)/arri)

chk=0
for i in range(n-k+1):
    chk=max(chk,sum(aa[i:i+k]))

print(chk)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,k=mii()
arra=limii()
arr=[]
s=[0]
chk=0
for i in range(n):
    arri=arra[i]
    arr.append((arri*(arri+1)//2)/arri)
    

for i in arr:s.append(s[-1]+i)

for i in range(n-k+1):
    chk=max(chk,s[i+k]-s[i])

print(chk)
### BUGGY CODE ###

N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1
 
memo_g = {}
def g(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_g:
        memo_g[(p, q)] = st_ed.get((p, q), 0) + g(p + 1, q)
    return memo_g[(p, q)]
 
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    return f(p, q - 1) + g(p, q)
 
memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])


### FIXED CODE ###

N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_g = {}
def g(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_g:
        memo_g[(p, q)] = st_ed.get((p, q), 0) + g(p + 1, q)
    return memo_g[(p, q)]

memo_f = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_f:
        temp = f(p, q - 1) + g(p, q)
        memo_f[(p, q)] = temp
    return memo_f[(p, q)]

memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

muki = 1
for i in Query:
    if i[0] == '1':
        muki *= -1
    else:
        if i[1] == '1':
            if muki == 1:
                S = i[2] + S
            else:
                S = S + i[2]
        else:
            if muki == -1:
                S = i[2] + S
            else:
                S = S + i[2]
if muki == -1:
    S = S[::-1]
print(S)
    



### FIXED CODE ###

S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

muki = 1
a = ''
b = ''
for i in Query:
    if i[0] == '1':
        muki *= -1
    else:
        if i[1] == '1':
            if muki == 1:
                a += i[2]
                # S = i[2] + S
            else:
                # S = S + i[2]
                b += i[2]
        else:
            if muki == -1:
                # S = i[2] + S
                a += i[2]
            else:
                # S = S + i[2]
                b += i[2]
S = a[::-1] + S + b
if muki == -1:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
Ans = 0


def xor(x, y):
    X = bin(max(x, y))
    Y = bin(min(x, y))
    w = bin(int(X, 2) ^ int(Y, 2))

    return int(w, 2)


for i in itertools.combinations(a, 2):
    Ans = Ans + xor(i[0], i[1])

print(Ans % mod)


### FIXED CODE ###

def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = tuple(map(int, input().split()))
mod = 10**9 + 7
cnt = [0] * 60
for i in range(n):
    r = a[i]
    for j in range(60):
        if r & 1:
            cnt[j] += 1
        r >>= 1

ans = 0
for i in range(60):
    ans += powmod(2, i, mod) * cnt[i] * (n-cnt[i])
    ans %= mod
print(ans)
### BUGGY CODE ###

n,m = map(int, input().split())
a = []
for i in range(m):
  a.append(list(map(int, input().split())))
 
b = []
for i in range(m):
  c = a[i][0]
  d = a[i][1]
  for e in range(c,d+1):
    b.append(e)

c = [t for t in set(b) if b.count(t) == m]

print(len(c))

### FIXED CODE ###

n,m = map(int, input().split())
a = []
b = []
c = []
for i in range(m):
  a.append(list(map(int, input().split())))
for i in range(m):
  b.append(a[i][0])
  c.append(a[i][1])
  
b_max = max(b)
c_min = min(c)

ans = max(0, min(c) - max(b) + 1)

print(ans)
### BUGGY CODE ###

N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append(i)
    l[b-1].append(i)
from collections import deque
q=deque([1])
e[0]=1
m=10**6
while q:
    pc=q.popleft()
    p,c=pc//m,pc%m
    for vn in AB[p]:
        x=1
        for en in l[vn-1]:
            if e[en]==0:
                if x==c:
                    x=c+1
                q.append(en*m+x)
                e[en]=x
                x+=1
print(*([max(e)]+e),sep='\n')

### FIXED CODE ###

N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append((b-1,i))
    l[b-1].append((a-1,i))
from collections import deque
q=deque([(AB[0][0]-1,1),(AB[0][1]-1,1)])
e[0]=1
M=1
while q:
    vp,c=q.popleft()
    x=1
    for vn,en in l[vp]:
        if e[en]==0:
            if x==c:
                x=c+1
            q.append((vn,x))
            e[en]=x
            M=max(M,x)
            x+=1
print(M)
print(*e,sep='\n')
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append([int(x) for x in input().split()])
B = [[True for i in range(N)] for j in range(N)]
A_sum = 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if i != k and j != k:
        if A[i][j] > (A[i][k] + A[k][j]):
          A_sum = -2
          break
        elif A[i][j] == (A[i][k] + A[k][j]):
          B[i][j] = False
          B[j][i] = False
if A_sum >= 0:
  for i in range(N):
    for j in range(N):
      if B[i][j]:
        A_sum += A[i][j]
print(A_sum // 2)


### FIXED CODE ###

import heapq
N = int(input())
A = [[] for i in range(N)]
Q = []
for i in range(N):
  A[i] = [int(x) for x in input().split()]
  for j in range(i + 1, N):
    heapq.heappush(Q, [A[i][j], i, j])
G = [[10 ** 9 + 1 for j in range(N)] for i in range(N)]
for i in range(N):
  G[i][i] = 0
cnt = 0
while Q:
  [d, s, t] = heapq.heappop(Q)
  add = True
  for k in range(N):
    if d > G[s][k] + G[k][t]:
      break
    if d == G[s][k] + G[k][t]:
      add = False
  else:
    G[s][t] = d
    G[t][s] = d
    cnt += d if add else 0
    continue
  print(-1)
  break
else:
  print(cnt)
### BUGGY CODE ###

n = int(input())
c = 0
ans = 1
for i in range(n):
	c += 1
	ans *= c
print (ans%(10**9+7))

### FIXED CODE ###

n = int(input())

num = 1
for i in range (n):
	num = (num*(i+1)) % (10**9 + 7)
print (num % 1000000007)
### BUGGY CODE ###

p=int(input())
a=[int(i) for i in input().split()]
b=[0 for i in range(p)]
#f(i)=ai
#(i,ai) 0<=i<p
#P(x)=sum range(p+1) ai fi(x)/fi(i)
#fi(i)=i!*(N-i-1)!
c=[0 for i in range(p+1)]
c[1]=-1
c[-1]=1
def inv(x):
    return pow(x,p-2,p)
def divide(k):
    #cを(x-k)で割る
    tmp=[c[i] for i in range(p+1)]
    res=[0 for i in range(p)]
    for i in range(p-1,-1,-1):
        res[i]=tmp[i+1]
        tmp[i]+=k*tmp[i+1]
        tmp[i]%=p
        #print(k,tmp,res)
    return res
#devide(i):fi(x)
Fact=[0 for i in range(p)]
Finv=[0 for i in range(p)]
Fact[0]=1
for i in range(p-1):
    Fact[i+1]=((i+1)*Fact[i])%p
Finv[p-1]=inv(Fact[p-1])
for i in range(p-1)[::-1]:
    Finv[i]=((i+1)*Finv[i+1])%p
ans=[0 for i in range(p)]
for i in range(p):
    fix=divide(i)
    fixiinv=(Finv[i]*Finv[p-i-1])%p
    fixiinv*=(-1)**(p-i-1)
    fixiinv%=p
    #print(fix,a[i],fixiinv)
    for j in range(p):
        ans[j]+=(((a[i]*fix[j])%p)*fixiinv)%p
        ans[j]%=p
print(*ans)


### FIXED CODE ###

p=int(input())
a=[int(i) for i in input().split()]
b=[0 for i in range(p)]
#f(i)=ai
#(i,ai) 0<=i<p
#P(x)=sum range(p+1) ai fi(x)/fi(i)
#fi(i)=i!*(N-i-1)!
c=[0 for i in range(p+1)]
c[1]=-1
c[-1]=1
def inv(x):
    return pow(x,p-2,p)
def divide(k):
    #cを(x-k)で割る
    tmp=[c[i] for i in range(p+1)]
    res=[0 for i in range(p)]
    for i in range(p-1,-1,-1):
        res[i]=tmp[i+1]
        tmp[i]+=k*tmp[i+1]
        tmp[i]%=p
        #print(k,tmp,res)
    return res
#devide(i):fi(x)
Fact=[0 for i in range(p)]
Finv=[0 for i in range(p)]
Fact[0]=1
for i in range(p-1):
    Fact[i+1]=((i+1)*Fact[i])%p
Finv[p-1]=inv(Fact[p-1])
for i in range(p-1)[::-1]:
    Finv[i]=((i+1)*Finv[i+1])%p
ans=[0 for i in range(p)]
for i in range(p):
    fix=divide(i)
    fixiinv=(Finv[i]*Finv[p-i-1])%p
    fixiinv*=(-1)**(p-i-1)
    fixiinv%=p
    #print(fix,a[i],fixiinv)
    for j in range(p):
        ans[j]+=(((a[i]*fix[j])%p)*fixiinv)%p
        ans[j]%=p
print(*ans)
### BUGGY CODE ###

N, M = map(int, input().split())

i = N
while M % i:
    i += 1

print(M//i)


### FIXED CODE ###

import math
N, M = map(int, input().split())

div = M
for i in range(1, int(math.sqrt(M))+1):
    if M % i:
        continue
    i2 = M // i
    if i >= N:
        div = min(div, i)
    if i2 >= N:
        div = min(div, i2)

print(M//div)
### BUGGY CODE ###

N = int(input())
sett = set()
L=[]
Dic = {}
for n in range(N):
    S = input()
    sett.add(S)
    L.append(S)


for i in list(sett):
    Dic[i]=0

for j in L:
    Dic[j] = Dic[j] + 1
    
max_k_list = [kv[0] for kv in Dic.items() if kv[1] == max(Dic.values())]
max_k_list = sorted(max_k_list)
for t in max_k_list:
    print(t)

### FIXED CODE ###

from collections import Counter
N = int(input())
L = [input() for _ in range(N)]
#for n in range(N):
    #S = input()
    #L.append(S)
Dic = Counter(L)
max_value = max(Dic.values())
max_k_list = [i for i, j in Dic.items() if j == max_value]
max_k_list = sorted(max_k_list)
for t in max_k_list:
    print(t)
### BUGGY CODE ###

N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]

A=0
B=0
for i in range(N):
  if i%2==0:
    D.sort(reverse=True, key=lambda x:x[0])
    tmp=[d for d in D if d[0]==D[0][0]]
    tmp.sort(reverse=True, key=lambda x:x[1])
    A+=tmp[0][0]
    D.remove(tmp[0])
  else:
    D.sort(reverse=True, key=lambda x:x[1])
    tmp=[d for d in D if d[1]==D[0][1]]
    tmp.sort(reverse=True, key=lambda x:x[0])
    B+=tmp[0][1]
    D.remove(tmp[0])
  
print(A-B)

### FIXED CODE ###

N = int(input())
D=[]
b=0
for _ in range(N):
  A,B=map(int, input().split())
  D.append([A,B,A+B])
  b+=B
D.sort(reverse=True, key=lambda x:x[2])

ans=0
while D!=[]:
  ans+=D[0][2]
  D.pop(0)
  if D!=[]:
    D.pop(0)
  
print(ans-b)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, mod = 10**5+2, 10**9+7
fac = [1] + [None] * N
for i in range(1, N+1):
    fac[i] = i * fac[i-1] % mod
def modCom(n, k):
    return 0 if n < k else fac[n] * pow(fac[k],mod-2,mod) * pow(fac[n-k],mod-2,mod) % mod
n = int(input())
a = list(map(int, input().split()))
for x in range(1, n+1):
    if a.count(x) == 2: break
fi = a.index(x) + 1
si = a[fi:].index(x) + fi + 1
print(n)
for k in range(2, n+1):
    print((modCom(n+1, k) - modCom(fi+n-si, k-1)) % mod)
print(1)


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N, mod = 10**5+1, 10**9+7
fac = [1, 1] + [None] * N
inv = [0, 1] + [None] * N
facInv = [1, 1] + [None] * N
for i in range(2, N+1):
    fac[i] = i*fac[i-1]%mod
    inv[i] = mod-(inv[mod%i]*(mod//i))%mod
    facInv[i] = facInv[i-1]*inv[i]%mod
def modCom(n, k):
    return 0 if n < k else fac[n] * facInv[k] * facInv[n-k] % mod
n = int(input())
a = list(map(int, input().split()))
dic = defaultdict(int)
for i, x in enumerate(a):
    if dic[x] > 0:
        fi = dic[x]
        si = i+1
        break
    dic[x] = i+1
print(n)
for k in range(2, n+1):
    print((modCom(n+1, k) - modCom(fi+n-si, k-1)) % mod)
print(1)
### BUGGY CODE ###

K = int(input())
def gcd(a, b):
    c = 1
    for i in range(1, min([a+1, b+1])):
        if a%i==0 and b%i==0:
            c = i
    return c

count = 0
for n in range(1, K+1):
    for m in range(1, K+1):
        for l in range(1, K+1):
            q = gcd(m, l)
            p = gcd(n, q)
            count += p
print(count)

### FIXED CODE ###

K = int(input())
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a%b
        a = b
        b = r
    return a
count = 0
temp = list()
for n in range(1, K+1):
    for m in range(1, n):
        temp.append(gcd(n, m))
for l in range(1, K+1):
    for j in range(len(temp)):
        p = gcd(l, temp[j])
        count += 2 * p
    for k in range(1, K+1):
        q = gcd(l, k)
        count += q
print(count)
### BUGGY CODE ###

from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
data = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
for i in range(M):
  id = list(range(data[i][0],data[i][1]+1))
  if i == 0:
      num = id
  else:
      num = set(num) & set(id)
print(len(num))

### FIXED CODE ###

from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
data = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
min_id =0
max_id = 100000
for i in range(M):
  min_id = max(min_id,data[i][0])
  max_id = min(max_id,data[i][1])
num = max_id - min_id + 1 if max_id - min_id >= 0 else 0
print(num)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
INF = 10**9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])
 
for i in range(2, N):
  for j in range(1, min(i, K) + 1):
    dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
for i, hi in enumerate(h):
  if i > 0:
    x = max(0, i - K)
    dp[i] = min([dpj + abs(hi - hj) for hj, dpj in zip(h[x:i], dp[x:i])])
print(dp[N - 1])
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
x = np.array([list(map(int, input().split())) for i in range(N)])
minprice = min(x[0:,0])
number = np.argmin(x[0:,0])
price = 0
cnt = 0
num = 0
while cnt < M:
    price += minprice
    cnt += 1
    num += 1
    if num == x[number][1] and (len(x) != 1):
        x = np.delete(x, number, 0)
        minprice = min(x[0:,0])
        number = np.argmin(x[0:,0])
        num = 0
print(price)


### FIXED CODE ###

N, M = map(int, input().split())
x = sorted([list(map(int, input().split())) for i in range(N)])
i = 0
minprice = x[i][0]
minnumber = x[i][1]
price = 0
while True:
    if M <= minnumber:
        price += minprice * M
        break
    else:
        price += minprice * minnumber
        M -= minnumber
        i += 1
        minprice = x[i][0]
        minnumber = x[i][1]
print(price)
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for x in range(Q):
    l[x], r[x] = list(map(int, input().split()))

isAC = [0] * len(S)
for x in range(len(S) - 1):
    if S[x] == "A" and S[x + 1] == "C":
        isAC[x] = 1

for x in range(Q):
    ans = 0
    cut_isAC = isAC[l[x] - 1:r[x] - 1]
    for y in range(len(cut_isAC)):
        ans += cut_isAC[y]
    print(ans)


### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for x in range(Q):
    l[x], r[x] = list(map(int, input().split()))

countAC = [0] * len(S)
for x in range(len(S) - 1):
    countAC[x + 1] = countAC[x]
    if S[x] == "A" and S[x + 1] == "C":
        countAC[x + 1] += 1
for x in range(Q):
    print(countAC[r[x] - 1] - countAC[l[x] - 1])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
answer = 1

for i in A:
    answer*=i

if answer > 10**18:
    print('-1')
else:
    print(answer)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
K=1
if 0 in A:
    print(0)
else:
    for num in A:
        K*=num
        if K>10**18:
            print(-1)
            exit()
    print(K)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    S,T,X=[0]*n,[0]*n,[0]*n
    D=[0]*q
    for i in range(n):
        S[i],T[i],X[i]=map(int,input().split())
    for j in range(q):
        D[j]=int(input())

    E=[]
    E+=[(s-x,1,x) for s,x in zip(S,X)]
    E+=[(t-x,2,x) for t,x in zip(T,X)]
    E+=[(d,3,i) for i,d in enumerate(D)]
    E.sort()
    cnt={x:0 for x in X}
    cnt[INF]=1

    from heapq import heappop,heappush
    Q=[INF]
    ans=[-1]*q
    for a,b,c in E:
        if(b==1):
            heappush(Q,c)
            cnt[c]+=1
        elif(b==2): # 本来はここでqからcを削除したいが、できないためb==3で処理する
            cnt[c]-=1
        else:
            while(cnt[Q[0]]==0): # 本来削除されるべき通行止めをここで消す
                heappop(Q)
            x=Q[0]
            if(x!=INF): ans[c]=x
    print(*ans,sep="\n")
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
read = sys.stdin.buffer.read
def resolve():
    n,q=map(int,input().split())
    data = list(map(int,read().split()))
    S = data[:3*n:3]
    T = data[1:3*n:3]
    X = data[2:3*n:3]
    D = data[3*n:]

    E=[]
    E+=[(s-x,1,x) for s,x in zip(S,X)]
    E+=[(t-x,2,x) for t,x in zip(T,X)]
    E+=[(d,3,i) for i,d in enumerate(D)]
    E.sort()
    from collections import defaultdict
    cnt=defaultdict(int)
    cnt[INF]=1

    from heapq import heappop,heappush
    Q=[INF]
    ans=[None]*q
    for a,b,c in E:
        if(b==1):
            heappush(Q,c)
            cnt[c]+=1
        elif(b==2): # 本来はここでqからcを削除したいが、できないためb==3で処理する
            cnt[c]-=1
        else:
            while(cnt[Q[0]]==0): # 本来削除されるべき通行止めをここで消す
                heappop(Q)
            x=Q[0]
            ans[c]=x if(x!=INF) else -1
    print(*ans,sep="\n")
resolve()
### BUGGY CODE ###

N = input()
a = []
for i in range(int(N)):
  x = input()
  TF = x in a
  if TF != True:
    a.append(x)
print(len(a))

### FIXED CODE ###

N = input()
n = int(N)
a = {input() for i in range(n)}  
print(len(a))
### BUGGY CODE ###

def dp(i):
    if i == 1 or i == 2:
        return 0
    elif i == 3 or i == 4:
        return 1
    else:
        return dp(i - 3) + dp(i - 1)


S = int(input())
print(dp(S))


### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

S = int(input())
ans = 0
mod = 10 ** 9 + 7
for i in range(1,700):
    x = S - 3 * i
    if x < 0:
        break
    ans += (combinations_count(x + i - 1, i - 1)) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    Ac = [-1 + 2 * int(A[i] >= mid) for i in range(n)]
    S = [0] * n
    S[0] = Ac[0]
    for i in range(n-1):
        S[i+1] = S[i] + Ac[i+1]
    bit = Bit(n+1)
    ans = 0


    Smin = min(S)
    S = [S[i]-min(S)+2 for i in range(n)]
    #print(S)
    for i, p in enumerate(S):
        bit.add(p, 1)
        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く

    #print(le, ri, mid, ans)

    if ans >= n*(n-1)//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)
    


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))

# n = 4
# A = [i+1 for i in range(n)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#print((n*(n+1))//(2*2))

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i+1] >= mid)
    bit = Bit(n+2)
    ans = 0
    for i in range(n):
        if S[i] >= 0:
            ans += 1

    #print("S OK")

    Smin = min(S)
    S = [S[i] - Smin + 1 for i in range(n)]

    #print("S OK2")
    #print(S)
    for i, p in enumerate(S):
        
        bit.add(p, 1)

        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く
        #print(i,ans)


    #print(le, ri, mid, ans)

    if ans >= (n*(n+1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)
### BUGGY CODE ###

N = int(input())
list1 = []
ind = 0
cnt = 0
top = 1
bot = 0
for i in range(N):
    L = list(map(int, input().split()))
    list1.append(L)
list1 = sorted(list1)
if list1[0][0]!=top:
    while(top!=list1[0][0]):
        cnt+=1
        top+=1
if list1[-1][1]!=bot:
    bot = list1[-1][1]
    while(bot!=0):
        cnt+=1
        bot-=1
for i in range(N-1):
    err = abs(list1[i][0]-list1[i+1][0])
    err1 = list1[i][1]-list1[i+1][1]
    if err != 1:
        cnt += min(err-1, err1-1)
print(cnt+N)

### FIXED CODE ###

N = int(input())
list1 = []
max1 = 0
for i in range(N):
    L = list(map(int, input().split()))
    if max1 < L[0]:
        max1 = L[0]
        ans = sum(L)
print(ans)