Harryxun/stf_run huggingface dataset:
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
    num += 1
    if S[i] == '0':
        cnt += 1
L.append(num)
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

### FIXED CODE ###

import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
        if S[i] == '0':
            cnt += 1
    num += 1
L.append(num)
if S[-1] == '0':
    cnt += 1
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = -float('inf')
for i in range(N):
    piece = i
    temp = 0
    hoge = []
    key = 0
    for j in range(N):
        piece = P[piece-1]
        temp += C[piece-1]
        hoge.append(temp)
        if j+1 > K:
            key = 1
            break
        if piece == i:
            break
    if key == 1:
        ans = max(ans,max(hoge))
    elif hoge[-1]<=0:
        ans = max(ans,max(hoge))
    else:
        d = K//len(hoge)
        r = K%len(hoge)
        peak = max(hoge[-1]*(d-1)+max(hoge[r:]),hoge[-1]*d+max(hoge[:r]))
        ans = max(ans,peak)
print(ans)



### FIXED CODE ###

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

ans = -float('inf')
v = []
for n in range(N):
    loop, score = 0, 0
    t = n
    for i in range(min(N, K)):
        n = P[n]-1
        score += C[n]
        ans = max(ans, score)
        if n == t:
            loop = i+1
            break
    v.append((loop, score))

for n in range(N):
    loop, score = v[n]
    if loop > 0 and score > 0:
        r = (K-1)//loop
        nscore = r*score
        for i in range(K-r*loop):
            n = P[n]-1
            nscore += C[n]
            ans = max(nscore, ans)
print(ans)
import numpy as np
N=list(map(int,input().split()))
A,B=max(N),min(N)
#ユーグリッド
GCD=1
while True:
    r=A%B
    if r==0:
        GCD=B
        break
    else:
        A=B
        B=r

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

_GCD=factorization(GCD)
num_list=[]
for num in _GCD:
    num_list+=[num[0]]*num[1]
ans_list=np.array([1])
for n in num_list:
    ans_list=np.r_[ans_list,ans_list*n]
#これで素因数分解の加工が完全に完了

count=0
while not list(ans_list) == [] :
    num=ans_list[0]
    if A%num==0 and B%num==0:
        count+=1
        if num==1:
            ans_list=ans_list[~(ans_list==1)]
        else:
            ans_list=ans_list[~(ans_list % num == 0)]
    else:
        ans_list=ans_list[~(ans_list % num == 0)]
        
print(count)

### FIXED CODE ###

import numpy as np
N=list(map(int,input().split()))
A,B=max(N),min(N)
#ユーグリッド
GCD=1
while True:
    r=A%B
    if r==0:
        GCD=B
        break
    else:
        A=B
        B=r

if GCD==1:
    print(1)
else:
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

        if arr==[]:
            arr.append([n, 1])

        return arr

    _GCD=factorization(GCD)
    num_list=[1]
    for num in _GCD:
        num_list+=[num[0]]
    #これで素因数分解の加工が完全に完了
    print(len(num_list))
def checker(x):
    if x < 2 or x % 2 == 0 :
        return False
    for i in range(2,x**0.5+1):
        if x % i == 0 :
            return False
    return True

cnt=0
q=int(input())
for _ in range(q):
    v=int(input())
    if checker(v):
        cnt += 1
print(cnt)

### FIXED CODE ###

def checker(x):
    if x == 2:
        return True
    if x < 2 or x % 2 == 0 :
        return False
    for i in range(2,int(x**0.5)+1):
        if x % i == 0 :
            return False
    return True

cnt=0
q=int(input())
for _ in range(q):
    v=int(input())
    if checker(v):
        cnt += 1
print(cnt)
import fractions
from functools import reduce
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]//2
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
f2=lcm_list(a)

ans=0
for i in range(n):
    if f2/a[i]%2!=1:
        print(ans)
        break
else:
    ans=m//f2
    print((ans+1)//2)

### FIXED CODE ###

import fractions
from functools import reduce
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]//2
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
f2=lcm_list(a)

ans=0
for i in range(n):
    if f2//a[i]%2!=1:
        print(ans)
        break
else:
    ans=m//f2
    print((ans+1)//2)
unchi

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, D = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d2=D**2
    cnt=0
    for x,y in S:
        if x**2+y**2<=d2:
            cnt+=1
    print(cnt)


if __name__ == "__main__":
    main()
n = int(input())
for i in range(1,n+1):
  x = i
  if x % 3 == 0 or x % 10 == 3:
    print(' {0}'.format(i), end='')
    continue

  x //= 10
  while x != 0:
    if x % 10 == 3:
      print(' {0}.format(i), end='')
    break

  x //= 10
print()

### FIXED CODE ###

n = int(input())
for i in range(3,n+1):
  x = i
  if x % 3 == 0:
    print(' {0}'.format(i), end='')
    continue

  while x != 0:
    if x % 10 == 3:
      print(' {0}'.format(i), end='')
      break
    x //= 10

print()
n = int(input())
ans = [-1]*n
data =[[] for i in range(n)]

for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    data[u].append([v,w])
    data[v].append([u,w])

ans[0] = 0
def color(i):
    for v,w in data[i]:
        if ans[v]== -1:
            if w%2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

color(0)
for i in range(n):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

n = int(input())
ans = [-1]*(n+1)
data =[[] for i in range(n+1)]

for i in range(n-1):
    u,v,w = map(int,input().split())
    data[u].append([v,w])
    data[v].append([u,w])

ans[1] = 1
def color(i):
    for v, w in data[i]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

color(1)
for i in range(n):
    print(ans[i+1])
n = int(input())
nums = []
for i in range(n):
  nums.append(int(input()))
cache = sorted(nums)
maximum = nums[0]
second = nums[1]
if maximum == second:
  flag = True
else:
  flag = False
for i in nums:
  if i == maximum && !flag:
    print(second)
  else:
    print(maximum)

### FIXED CODE ###

r = input()
print(int(r)**2 * 3)
x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]
S = S[::-1]

dp = [[0 for j in range(13)] for i in range(len(S) + 1)]

dp[0][0] = 1

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

        digit_r = ((10 ** i) * j) % 13

        for k in range(13):
            r = (digit_r + k) % 13
            dp[i + 1][r] += dp[i][k]

    dp[i + 1][r] %= x

print(int(dp[-1][5] % x))


### FIXED CODE ###

A, B = map(int, input().split())

K = (A + B) / 2

if int(K) == K:
    print(int(K))
else:
    print('IMPOSSIBLE')
from collections import defaultdict
import os
def debug(*args): print(*args, file=sys.stderr)# os.environ.get("USER")
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
#print(dd)
B=sorted(A,reverse=True)
ans=0
for x in B:
    debug(A)
    #print(x)
    if dd.get(x,-1)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            #print(ans)
            #print(dd)
    else:
        s+=1
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        # if used[mid]:
        #     res = bisect(val, mid+1, end)
        #     if res is not None:
        #         return res
        #     res = bisect(val, start, mid)
        #     return res
        # else:
        #     used[mid] = True
        #     debug("fuga", used)
        #     return mid
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i]  == val):
    #         used[i] = True
    #         return i
    return None


def _find(b, end, e):
    "slow!!!!"
    # debug(b, end, e)
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i] + b == 2**e):
    #         used[i] = True
    #         return i
    # return None


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        ans += 1


print(ans)
class Bit:
    def __init__(self, n):
        sz = 1
        while n >= sz:
            sz *= 2
        self.size = sz
        self.data = [0]*sz

    def sum(self, i):
        assert i > 0
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        assert i > 0
        while i < self.size:
            self.data[i] += x
            i += i & -i

import bisect
N = int(raw_input())
a = [int(x)-1 for x in raw_input().split()]
weight = [1] * N
M = 10**9+7
def factorial(n):
    acc = 1
    for i in xrange(1, 1 + n):
        acc = (acc * i) % M
    return acc
def inv(n):
    return pow(n, M-2, M)
for i in xrange(N-1):
    weight[N-2-i] = (weight[N-1-i] * (i+1)) % M
missing = list(set(xrange(N)) - set(a))
missing.sort()
n_missing = len(missing)
sum_missing = sum(missing)
avg_missing = sum_missing * inv(n_missing)
n_present = N - n_missing
n_rows = factorial(n_missing)
acc = 0
i_missing = 0
i_present = 0
missing_lt_tot = 0
#present_values = []
present_values_bit = Bit(N+5)
inv_n_missing = inv(n_missing)
inv_2 = inv(2)
for i, (w, x) in enumerate(zip(weight, a)):
    if x == -1:
        ai = avg_missing
        bi = (i_missing * inv_2 + i_present - missing_lt_tot * inv_n_missing) % M
        i_missing += 1
    else:
        ai = x
        #bi = sum(1 for present_value in present_values if present_value < x)
        bi = present_values_bit.sum(x + 1)
        #present_values.append(x)
        present_values_bit.add(x + 2, 1)
        '''
        missing_lt = 0
        for j in missing:
            if j < a[i]:
                missing_lt += 1
        '''
        missing_lt = bisect.bisect(missing, a[i])
        missing_lt_tot += missing_lt
        #print '@', missing_lt, n_missing, i_missing, n_rows
        bi += missing_lt * inv_n_missing * i_missing
        bi %= M
        i_present += 1
    #print x, (ai * n_rows) % M, (bi * n_rows) % M, w
    acc = (acc + (((ai - bi) * n_rows) % M) * w) % M
print (acc + n_rows) % M


### FIXED CODE ###

H, W = map(int, raw_input().split())
a = [raw_input().strip() for _ in xrange(H)]
a = map(''.join, zip(*a))
ans = 0
def solve(a, c):
    shift = [[0] * (H+1) for _ in xrange(H+1)]
    for i in reversed(xrange(H)):
        for j in reversed(xrange(H)):
            shift[i][j] = shift[i+1][j+1] + int(a[H-1-i] == c[H-1-j])
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = b
    #print a, c, shift
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans
# coding :utf-8
N=int(input())

F=[]
P=[]

table = [2**i for i in range(10)]
#print(table)

for i in range(N):
    lis = list(map(int, input().split()))
    F.append(lis)
#print(F)
for i in range(N):
    lis = list(map(int, input().split()))
    P.append(lis)
#print(P)

max=-1000000000001

for i in range(1,1024):
    total=0
    for j in range(N):
        n=0
        for k in range(10):
            n +=(1 if i&table[k] !=0 else 0)*F[j][t]
        total += P[j][n]
    if total >maxx:
        maxx= total
print(maxx)

### FIXED CODE ###

# coding :utf-8
N=int(input())

F=[]
P=[]

table = [2**i for i in range(10)]
#print(table)

for i in range(N):
    lis = list(map(int, input().split()))
    F.append(lis)
#print(F)
for i in range(N):
    lis = list(map(int, input().split()))
    P.append(lis)
#print(P)

maxx=-1000000000001

for i in range(1,1024):
    total=0
    for j in range(N):
        n=0
        for k in range(10):
            n +=(1 if i&table[k] !=0 else 0)*F[j][k]
        total += P[j][n]
    if total >maxx:
        maxx= total
print(maxx)
n = int(input())
a = list(map(int, input().split()))
b = a[0::2][::-1]
c = a[1::2]

b.extend(c)
print(*b[::-1] if n % 2 == 0 else *b)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = a[0::2][::-1]
c = a[1::2]

b.extend(c)
if n % 2 == 0:
    b = b[::-1]
print(*b)
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return True
    else:
        pair[rx] = ry

def same(x, y):
    rx = root(x)
    ry = root(y)
    return rx == ry

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(M):
    x, y, z = map(int, input().split())
    unite(x, y)

cnt = set()
for k, y in pair.items():
    ry = root(y)
    cnt.add(ry)
print(len(cnt))


### FIXED CODE ###

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

tmp = []
for i in range(M):
    tmp.append(list(map(int, input().split())))
tmp.sort()
for i in range(M):
    x, y = tmp[i][0], tmp[i][1]
    if x < y:
        unite(x, y)
    else:
        unite(y, x)

cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    s = input() # 暗号
    t = input() # 含まれる文字

    s_len = len(s)
    t_len = len(t)

    for i in range(s_len - t_len,-1,-1):
        flg = True
        for j in range(t_len):
            if s[i+j] != t[j] and s[i+j] != "?":
                flg = False
                break
        if flg == True:
            flg = i
            break

    if flg == False:
        print("UNRESTORABLE")
        exit()

    ans = ""
    for i in s[:flg]:
        if i == "?":
            ans = ans + "a"
        else:
            ans = ans + i
    ans = ans + t
    print(ans)

    for i in s[(flg+t_len):]:
        if i == "?":
            ans = ans + "a"
        else:
            ans = ans + i

    print(ans)














if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    s = input() # 暗号
    t = input() # 含まれる文字

    s_len = len(s)
    t_len = len(t)
    flg = False

    for i in range(s_len - t_len,-1,-1):
        flg = True
        for j in range(t_len):
            if s[i+j] != t[j] and s[i+j] != "?":
                flg = False
                break
        if flg == True:
            trial = i
            break

    if flg == False:
        print("UNRESTORABLE")
        exit()

    ans = ""
    for i in s[:trial]:
        if i == "?":
            ans = ans + "a"
        else:
            ans = ans + i
    ans = ans + t

    for i in s[(trial+t_len):]:
        if i == "?":
            ans = ans + "a"
        else:
            ans = ans + i

    print(ans)














if __name__=="__main__":
    main()
n = int(input())
L,R = [0]*n,[0]*n
for i in range(n):
    L[i],R[i] = map(int,input().split())
    R[i] += 1

M = L.index(max(L))
m = R.index(min(R))

d = [R[i] - L[i] if M != i != m else 0 for i in range(n)]
ans = max(d) + max(R[m] - L[M], 0)
d[m] = R[m] - L[m]
d[M] = R[M] - L[M]
if m == M:
    print(ans)
    exit()
if n == 2:
  print(d[m] + d[M])
a,b = [0]*(n-2),[0]*(n-2)
j = 0
for i in range(n):
    if m != i != M:
        a[j],b[j] = max(R[i]-L[M],0) , -max(R[m]-L[i],0)
        j += 1
ab = sorted(list(zip(a,b)),reverse = True)
mb = [0]*len(a)
for i in range(len(a))[::-1]:
    if i == len(a)-1:
        mb[i] = -ab[i][1]
    else:
        mb[i] = min(-ab[i][1], mb[i+1])
for i in range(len(a) - 1):
    ans = max(ans,min(a[i],d[M]) + min(mb[i + 1],d[m]))
ans = max(ans , d[M] + min(mb[0], d[m]), min(a[len(a)-1],d[M]) + d[m])

print(ans)


### FIXED CODE ###

n = int(input())
L,R = [0]*n,[0]*n
for i in range(n):
    L[i],R[i] = map(int,input().split())
    R[i] += 1

M = L.index(max(L))
m = R.index(min(R))

d = [R[i] - L[i] if M != i != m else 0 for i in range(n)]
ans = max(d) + max(R[m] - L[M], 0)
d[m] = R[m] - L[m]
d[M] = R[M] - L[M]
if m == M:
    print(ans)
    exit()
if n == 2:
    print(d[m] + d[M])
    exit()
a,b = [0]*(n-2),[0]*(n-2)
j = 0
for i in range(n):
    if m != i != M:
        a[j],b[j] = max(R[i]-L[M],0) , max(R[m]-L[i],0)
        j += 1
ab = sorted(list(zip(a,b)),reverse = True)
mb = [0]*len(a)
for i in range(len(a))[::-1]:
    if i == len(a)-1:
        mb[i] = ab[i][1]
    else:
        mb[i] = min(ab[i][1], mb[i+1])
for i in range(len(a) - 1):
    ans = max(ans,min(ab[i][0],d[M]) + min(mb[i + 1],d[m]))
ans = max(ans , d[M] + min(mb[0], d[m]), min(ab[len(a)-1][0],d[M]) + d[m])

print(ans)
#入力,準備
n=int(input())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
W=int(input())
dp=[0]*(W+1)

#メイン
#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1

print(dp[W])

### FIXED CODE ###

N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print(dp[W])