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

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = map(str, input().split())
    t.append(ti)
    d.append(di)
    
LEFT_DIE = -1
RIGHT_DIE = len(s)

def is_dead(i):
    for ti, di in zip(t, d):
        if s[i] == ti:
            if di == 'L':
                i -= 1
            if di == 'R':
                i += 1
            if i == LEFT_DIE:
                return LEFT_DIE
            if i == RIGHT_DIE:
                return RIGHT_DIE
    return 0

low = -1
high = len(s);
# LEFT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == LEFT_DIE:
        low = mid
    else:
        high = mid
left_edge = high

low = -1
high = len(s);
# RIGHT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == RIGHT_DIE:
        high = mid
    else:
        low = mid
right_edge = low

#print(left_edge, right_edge)
ans_s = s[left_edge:right_edge+1]
#print(ans_s)
ans = len(ans_s)
print(ans)

        
        
        
        
        
        

### FIXED CODE ###

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = input().split()
    t.append(ti)
    d.append(di)
    
LEFT_DIE = -1
RIGHT_DIE = N

def is_dead(i):
    for ti, di in zip(t, d):
        if s[i] == ti:
            if di == 'L':
                i -= 1
            if di == 'R':
                i += 1
            if i == LEFT_DIE:
                return LEFT_DIE
            if i == RIGHT_DIE:
                return RIGHT_DIE
    return 0

low = -1
high = N;
# LEFT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == LEFT_DIE:
        low = mid
    else:
        high = mid
left_edge = high

low = -1
high = N;
# RIGHT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == RIGHT_DIE:
        high = mid
    else:
        low = mid
right_edge = low

#print(left_edge, right_edge)
ans_s = s[left_edge:right_edge+1]
#print(ans_s)
ans = len(ans_s)
print(ans)
### BUGGY CODE ###

import sys

n=int(sys.stdin.readline())
a,b,M = [0]*n,[0]*n,[]
for i in range(n):
    a[i],b[i] = map(int,sys.stdin.readline().split())
    M.append(a[i]+b[i])

cnt = 0
tflg = True
for i in range(n):
    mat = min(M)
    id = M.index(mat)
    if tflg:
        cnt += a[id]
    else:
        cnt -= b[id]
    tflg = not(tflg)
    M.pop(id)
    a.pop(id)
    b.pop(id)
print(cnt)


### FIXED CODE ###

import sys

n=int(sys.stdin.readline())
M = []
for i in range(n):
    a,b = map(int,sys.stdin.readline().split())
    M.append([a,b])

M = sorted(M,key=lambda x:sum(x), reverse=True)
cnt = 0
for i in range(n):
    if i%2==0:
        cnt += M[i][0]
    else:
        cnt -= M[i][1]
print(cnt)
### BUGGY CODE ###

import itertools as it

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

ans = 0
for ith_conf in it.product(range(2), repeat=N):
    dif = 0
    for j_jewel in range(N):
        if ith_conf[j_jewel] == 1:
            dif += V[j_jewel] - C[j_jewel]
    ans = max(ans, dif)
print(ans)


### FIXED CODE ###

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
ans = 0
for i in range(N):
    if V[i] > C[i]:
        ans += V[i] - C[i]
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A = []
B = []
count = 0
sum = 0

for i in range(N):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)
 
while(count < M):
  min_price = min(A)
  min_index = A.index(min_price)
  A_buy_num = B[min_index]
  if((count + A_buy_num)  <= M):
   count += A_buy_num
   sum += (A.pop(min_index))*(B.pop(min_index))
  else: #(count + A_buy_num)  > M
   rest_num = M - count 
   count += rest_num
   sum += (A.pop(min_index))*(rest_num)
   break

print(sum)
  


### FIXED CODE ###

N,M = map(int,input().split())
AB = []
count = 0
sum = 0

for i in range(N):
  a,b = map(int,input().split())
  s = [a,b]
  AB.append(s)
  
AB.sort()
i = 0
while(1):
  if(count >= M):
    break  
  if((count + AB[i][1]) <= M):
   sum += AB[i][0]*AB[i][1]
   count += AB[i][1]
  else:
    rest = M - count
    sum += AB[i][0]*rest
    break
  i += 1

print(sum)
### BUGGY CODE ###

N=int(input())
count=0
S=input()
for i in range(N):
    for j in range(i,N):
        if S[i]==S[j]:
            continue
        for k in range(j,N):
            if j-i!=k-j:
                if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                    count+=1
print(count)

### FIXED CODE ###

N=int(input())
S=input()
R=S.count("R")
G=S.count("G")
B=S.count("B")
ans=R*G*B
for i in range(N):
    for j in range(i,N):
        k=j+j-i
        if k>=N:
            continue
        if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
            ans-=1
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
g = [str(input()) for _ in range(H)]
ans = 0
for h in range(H):
    for w in range(W):
        if g[h][w] != '#':
            cnt = 1
            dh = [1, -1, 0, 0]
            dw = [0, 0, 1, -1]
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                while True:
                    if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                        cnt += 1
                        nh += dh[i]
                        nw += dw[i]
                    else:
                        break
            ans = max(ans, cnt)
print(ans)


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    g = [str(input()) for _ in range(H)]
    LW = [[0] * W for _ in range(H)]
    LH = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LW[h][w-i] = cnt
                LW[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LW[h][w-i] = cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LH[h-i][w] = cnt
                LH[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LH[h-i][w] = cnt
    ans = 0
    for h in range(H):
        for w in range(W):
            if g[h][w] != '#':
                ans = max(ans, LH[h][w] + LW[h][w] - 1)
    print(ans)
main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import Counter
N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
BC=[map(int, sys.stdin.readline().split()) for _ in range(M)]

C=Counter(A)
A=C.items()
heapify(A)    #(カードの数字、カード枚数)

for b,c in BC:
    while A[0][0]<c and 0<b:
        value=A[0][0]
        cards=A[0][1]
        heappop(A)
        if cards<=b:    #取った枚数以上に手元の枚数を持っていれば、カードを全交換できる
            heappush(A,(c,cards))
        else:     #手元の方が少ない場合
            heappush(A,(c,b))   #新しいカードの値を挿入
            heappush(A,(value,cards-b))   #取ったカードも一部元に戻す
        b-=cards

ans=0
for a,cards in A:
    ans+=a*cards
print ans

### FIXED CODE ###

import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

B=[ map(int, sys.stdin.readline().split()) for _ in range(M)] 
B.sort(key=lambda x: x[1], reverse=True)

i=0

for b,c in B:
	for i in range(i,N):
		if A[i]<c and 0<b:
			A[i]=c
			b-=1
		if b==0:
			break
	i+=1

print sum(A)
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
ans=0
for i in range(n):
  for j in range(i+1,n+1):
    ans+=sum(s[i:j])==0
print(ans)

### FIXED CODE ###

def main():
    import sys
    from itertools import accumulate
    from collections import Counter

    n = int(input())
    a = list(map(int, sys.stdin.readline().split()))
    b = [0] + list(accumulate(a))
    c = Counter(b)

    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

#縦k、横kのマスに移動させて考える
n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i]):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i]):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

### FIXED CODE ###

import sys

#縦k、横kのマスに移動させて考える
n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
graph[0][0] += lx
for i in range(lx):
    graph[x[i]][0] -= 1
    graph[0][y[i]] -= 1
    graph[x[i]][y[i]] += 2

lmx = len(mx)
graph[0][0] -= lmx
for i in range(lmx):
    graph[mx[i]][0] += 1
    graph[0][my[i]] += 1
    graph[mx[i]][my[i]] -= 2

for i in graph:
    for j in range(k-1):
        i[j+1] += i[j]

for i in range(k):
    for j in range(k-1):
        graph[j+1][i] += graph[j][i]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)
### BUGGY CODE ###

def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

def LCM(m,n):
  for i in range(1,m+1)[::-1]:
    if n%i==0:
      return i
    
N,X=(int(i) for i in input().split(' '))
x=[int(i) for i in input().split(' ')]
x=[X]+x
x=quick_sort(x)
D=abs(x[1]-x[0])
for i in range(N):
  D=LCM(D,abs(x[i+1]-x[i]))
print(D)


### FIXED CODE ###

def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

def LCM(m,n):
  if m>n:
    m,n=n,m
  for i in range(1,m+1)[::-1]:
    if n%i==0:
      return i
    
N,X=(int(i) for i in input().split(' '))
x=[int(i) for i in input().split(' ')]
x=[X]+x
x=quick_sort(x)
D=abs(x[1]-x[0])
for i in range(N):
  D=LCM(D,abs(x[i+1]-x[i]))
print(D)
### BUGGY CODE ###

S=input()
Q=int(input())
for i in range(Q):  
  L=list(input().split())
  if L[0]=="1":
    S=S[::-1]
  else:
    if L[1]=="1":
      S=L[2]+S
    else:
      S=S+L[2]
print(S)

### FIXED CODE ###

import collections

s = collections.deque(list(input()))
q = int(input())
rev = 0
for i in range(q):
    tfc = list(input().split())
    if tfc[0]=='1':
        rev = abs(rev-1)
    else:
        t,f,c = tfc
        if rev:
            if f=='1':
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if f=='1':
                s.appendleft(c)
            else:
                s.append(c)
if rev:
    t = []
    for i in range(len(s)):
        t.append(s.pop())
    print(''.join(t))
else:
    print(''.join(s))
'''
初期文字列 s が与えられ q 個のクエリを処理した後の文字列を求めます。
10^100回繰り返す根気があるなら自分でやってくれと思わなくもないです。
さて、各クエリではまず t が与えられます。t=1の時文字列を反転させます。
t=2の時はさらに f,c が与えられ、f=1の時文字列の先頭にcを加えます。
f=2の時文字列の末尾にcを加えます。
愚直に行おうとすると文字列の反転で O(len(s))、先頭への追加で 
O(len(s)) かかってしまい間に合いません。
そこでcollections.dequeを利用します。先頭、末尾への追加をO(1) で行えます。
注意する点は反転させると追加する位置が逆になることです。
なので現在の状態を管理しておく必要があります。
同様に出力する時も最終的な向きによって出力する順番が逆になります。
'''
### BUGGY CODE ###

from heapq import heappush, heappop

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
used = [[[False] * (z + 1) for _ in range(y + 1)] for _ in range(x + 1)]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
kouho = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]


def calc(a, b, c):
    if not used[a][b][c]:
        used[a][b][c] = True
        heappush(kouho, ((-A[a] - B[b] - C[c]), a, b, c))


used[0][0][0] = True
for i in range(k):
    temp, p, q, r = heappop(kouho)
    temp *= -1
    print(temp)
    if p + 1 < x:
        calc(p + 1, q, r)
    if q + 1 < y:
        calc(p, q + 1, r)
    if r + 1 < z:
        calc(p, q, r + 1)


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
goukei = []
for a in A:
    for b in B:
        goukei.append(a + b)
goukei.sort()
goukei2 = goukei[-k:]
goukei3 = []
for c in C:
    for ab in goukei2:
        goukei3.append(ab + c)
goukei3.sort(reverse=True)
print(*goukei3[:k], sep="\n")
### BUGGY CODE ###

s=input()
a=len(s)
b=10**5+1
while True:
#    print(a,b)
    b=len(s)
    s=s.replace("10","")
    s=s.replace("01","")
    c=len(s)
    if c==b:
        break
print(a-c)

### FIXED CODE ###

s=input()
print(len(s)-abs(s.count("1")-s.count("0")))
### BUGGY CODE ###

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

l_set = set(l)
syukei = []
for i in l_set:
    syukei.append(l.count(i))
    syukei.sort()
    
if len(syukei)-K > 0:
    print(sum(syukei[:len(syukei)-K]))
else:
    print(0)

### FIXED CODE ###

import collections
N, K = map(int, input().split())
l = list(input().split())

c = collections.Counter(l)
c = c.most_common()
cnt = 0
if len(c) - K > 0:
    for i in range(1 , len(c) - K + 1):
        cnt += c[-i][1]

print(cnt)
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(n):
    s.append(input())
s=sorted(s)
ss=sorted(list(set(s)))
m=0
t=[]
for i in ss:
    tm=s.count(i)
    t.append(tm)
    m=max(m,tm)

for i in ss:
    if(m==s.count(i)):print(i)

### FIXED CODE ###

n=int(input())
s=[]
m={}
for i in range(n):
    st=input()
    if(st in m):m[st]+=1
    else:m[st]=1
mx=max(m.values())
ans=[]
for i in m:
    if(m[i]==mx):ans.append(i)
ans=sorted(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)[::-1]

ans = 0


for a in range(n):
    fl = 0
    A = l[a]

    for b in range(a+1,n):
        B = l[b]
        if A > B*2:
            break
        for c in range(b+1,n):

            C = l[c]

            if A >= B + C:
                break

            ans += 1

print(ans)

### FIXED CODE ###

import bisect

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)

ans = 0

for a in range(n):
    fl = 0
    A = l[a]
    for b in range(a+1,n):
        B = l[b]

        idx = bisect.bisect_left(l, A+B)
        ans += max(0,idx-b-1)

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

N,K = map(int, input().split())
p = list(map(int, input().split()))
Max = []
E = 0.0

for i in range(N-(K-1)):
    if sum(Max) < sum(p[i:i+K:]):
        Max = p[i:i+K:]

for num in Max:
    E += (num+1)* num //2/num

print(E)


### FIXED CODE ###

from collections import deque
import copy
N,K = map(int, input().split())
p = list([(i+1)* i/2/i for i in map(int, input().split())])
que = deque([0]* K)
sumM = 0
sumq = 0
E = 0.0

for i in range(N):
    sumq -= que.popleft()
    sumq += p[i]
    que.append(p[i])
    if E < sumq:
        E = sumq
print(E)
### BUGGY CODE ###

from collections import defaultdict
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

d = defaultdict(int)

# マスの数が5000以下であるため、KがNより大きい場合必ずループする
# それぞれのますが何回移動してからループに入るかを調べ残す
for i in range(N):
    idx = P[i]
    count = 0
    score = 0
    new_K = K
    while new_K > 0:
        # if (idx == P[i] and count != 0):
        #     break
        score += C[idx - 1]
        if (d[i + 1] == 0):
            d[i + 1] = score
        else:
            d[i + 1] = max(d[i + 1], score)
        idx = P[idx - 1]
        count += 1
        new_K -= 1


ans = -1 * 10 ** 10 + 7
for v in d.values():
    ans = max(ans, v)

print(ans)


### FIXED CODE ###

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

# 一度たずねた場所はループが判明しているのでそのままにする(何度移動させるかに関係なくtree構造がつながっているかを調べたい)
ans = -10 ** 18
for i in range(N):
    x = i
    loop = []
    total = 0
    while True:
        x = P[x] - 1
        loop.append(C[x])
        total += C[x]
        if x == i:
            break

    T = len(loop)
    tmp = 0
    for j in range(T):
        tmp += loop[j]
        if K < j + 1:
            break
        now = tmp
        # 一周のループが正の時のみ何度も回す価値がある。それ以外のときはそれまでの最大をとる
        if total > 0:
            loop_times = (K - (j + 1)) // T
            now += total * loop_times

        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

S = list(input())
N = len(S)

marker = [0] * N
for i in range(1, N - 1):
    if S[i] == "R" and S[i + 1] == "L":
        marker[i] = 1
    elif S[i - 1] == "R" and S[i] == "L":
        marker[i] = 2
    else:
        marker[i] = 0
marker[0] = 1 if S[1] == "L" else 0
marker[-1] = 2 if S[-2] == "R" else 0

cp = list(range(N))
p_last = [-1] * N   # ループに入る最初の座標
steps = [0] * N     # p_lastに着くまでのステップ数
dests = [0] * N     # 1: p_lastがR; 2: L
for i in range(N):
    s = 0
    cp = i
    while True:
        if p_last[cp] >= 0:
            p_last[i] = p_last[cp]
            steps[i] = s + steps[cp]
            dests[i] = marker[p_last[cp]]
            break
        elif marker[cp] == 0:
            s += 1
            if S[cp] == "R":
                cp += 1
            else:
                cp -= 1
        else:
            p_last[i] = cp
            steps[i] = s
            dests[i] = marker[cp]
            break

count = [0] * N
for i in range(N):
    pl = p_last[i]
    if dests[i] == 1:
        if steps[i] % 2 == 0:
            count[pl] += 1
        else:
            count[pl + 1] += 1
    else:
        if steps[i] % 2 == 0:
            count[pl] += 1
        else:
            count[pl - 1] += 1
print(" ".join(str(c) for c in count))

### FIXED CODE ###

S = list(input())
N = len(S)

marker = [0] * N
for i in range(1, N - 1):
    if S[i] == "R" and S[i + 1] == "L":
        marker[i] = 1
    elif S[i - 1] == "R" and S[i] == "L":
        marker[i] = 2
    else:
        marker[i] = 0
marker[0] = 1 if S[1] == "L" else 0
marker[-1] = 2 if S[-2] == "R" else 0

cp = list(range(N))
p_last = [-1] * N   # ループに入る最初の座標
steps = [0] * N     # p_lastに着くまでのステップ数
dests = [0] * N     # 1: p_lastがR; 2: L
for i in range(N):
    s = 0
    cp = i
    hist = []   # 訪れた座標
    hist_append = hist.append
    while True:
        if p_last[cp] >= 0:
            p_last[i] = p_last[cp]
            steps[i] = s + steps[cp]
            dests[i] = marker[p_last[cp]]
            break
        elif marker[cp] == 0:
            s += 1
            if S[cp] == "R":
                cp += 1
            else:
                cp -= 1
            hist_append(cp)
        else:
            p_last[i] = cp
            steps[i] = s
            dests[i] = marker[cp]
            break

    for j, h in enumerate(hist[::-1], 1):
        p_last[h] = p_last[i]
        steps[h] = steps[i] - j
        dests[h] = dests[i]

count = [0] * N
for i in range(N):
    pl = p_last[i]
    if dests[i] == 1:
        if steps[i] % 2 == 0:
            count[pl] += 1
        else:
            count[pl + 1] += 1
    else:
        if steps[i] % 2 == 0:
            count[pl] += 1
        else:
            count[pl - 1] += 1
print(" ".join(str(c) for c in count))
### BUGGY CODE ###

#再思考
n, m ,k = map(int, input(). split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a_sum = [0] * (n + 1)
b_sum = [0] * (m + 1)
for i in range(n):
    a_sum[i + 1] = a_sum[i] + a[i]
for i in range(m):
    b_sum[i + 1] = b_sum[i] + b[i]
res = 0
for i in range(n+1):
    for j in range(m+1):
        if a_sum[i] + b_sum[j] <= k:
            res = max(res, i + j)
        else:
            break
print(res)

### FIXED CODE ###

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

a_num = 0
b_num = 0
book_num = 0
passed_k = 0
for i in range(n):
    if a[i] + passed_k <= k:
        a_num += 1
        passed_k += a[i]
    else:
        break
for i in range(m):
    if b[i] + passed_k <= k:
        b_num += 1
        passed_k += b[i]
    else:
        break
book_num = a_num + b_num

while a_num > 0:
    passed_k -= a[a_num - 1]
    a_num -= 1
    while b_num < m:
        if passed_k + b[b_num] <= k:
            passed_k += b[b_num]
            b_num += 1
        else:
            break
    book_num = max(book_num, a_num + b_num)
    if b_num == m:
        break

print(book_num)
### BUGGY CODE ###

a,b=list(map(int,input().split()))
count=0
for x in range(a+1):
    for y in range(a+1):
        for z in range(a+1):
            if x+y+z == b:
                count+=1
print(count)

### FIXED CODE ###

a,b=list(map(int,input().split()))
count=0
for x in range(a+1):
    for y in range(a+1):
        if b < x+y:
            break
        if b-x-y <= a:
            count+=1
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(m)]
l=[int(i) for i in range(1,n+1)]
for x in a:
    l=set(l)&set([int(i) for i in range(x[0],x[1]+1)])
print(len(l))

### FIXED CODE ###

n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(m)]
b=0
s=100000000000
for x in a:
    b=max(b,x[0])
    s=min(s,x[1])
print(max(0,s-b+1))