Harryxun/stf_run huggingface dataset:
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b


N, M = map(int, input().split())
S = input()
T = input()
x = gcd(N, M)
n = N // x
m = M // x

for i in range(3):
    if S[n*i] == T[m*i]:
        print(-1)
        break
print(N*M//x)


### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b


N, M = map(int, input().split())
S = input()
T = input()
x = gcd(N, M)
n = N // x
m = M // x

for i in range(x):
    if S[n*i] != T[m*i]:
        print(-1)
        exit()
print(N*M//x)
a, b, c = map(int, input().split(None, 2))

print(a+b+c)


### FIXED CODE ###

print(input().count("1"))
input_num = input()
input = input().split()

times = 0
i = 0

while True:
  if int(input[i]) % 2 == 0:
    i += 1
    if i == input_num:
      i = 0
      times += 1
  else:
    break

print(times)

### FIXED CODE ###

input_num = input()
input = input().split()

times = 0
i = 0
    
while True:
  if int(input[i]) % 2 == 0:
    input[i] = int(input[i]) / 2
    i += 1
    if i == int(input_num) - 1:
      i = 0
      times += 1
  else:
    break
print(times)
n = int(input())
sum = 0
for k in range(n):
  for j in range(k):
  	if k % j == 0：
    	sum += k
print(sum)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    y = n // i
    ans += y * (y + 1) * i // 2
print(ans)
X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
s = []

for i in A:
	for j in B:
		for k in C:
			s.append(i+j+k)

s = sorted(s, reverse=True)

for i in range(K):
	print s[i]

### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
e = []
s = []

for i in A:
    for j in B:
        e.append(i+j)
e = sorted(e, reverse=True)

if K<len(e):
    e = e[0:K]

for i in e:
    for j in C:
        s.append(i+j)

s = sorted(s, reverse=True)

for i in range(K):
    print(s[i])
# -*- coding: utf-8 -*-
import math


def main():
    n, y = map(int, input().split())

    a, b, c = -1, -1, -1
    for ia in range(n + 1):
        for ib in range(n - ia + 1):
            ic = n - ia - ib
            total = ia * 10000 + ib * 5000 + ic * 1000
            if total == y and (ia + ib + ic) == n:
                a = ia
                b = ib
                c = ic
                break

    print(f"{a} {b} {c}")


if __name__ == '__main__':
    main()




### FIXED CODE ###

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


def main():
    n, y = map(int, input().split())

    a, b, c = -1, -1, -1
    for ia in range(n + 1):
        for ib in range(n - ia + 1):
            ic = n - ia - ib
            total = ia * 10000 + ib * 5000 + ic * 1000
            if total == y and (ia + ib + ic) == n:
                a = ia
                b = ib
                c = ic
                break

    print(" ".join(map(str, (a, b, c))))


if __name__ == '__main__':
    main()
import sys
import numpy as np


def main():
    x, y, z, k = [int(n) for n in input().split()]
    a = sorted([int(n) for n in input().split()], reverse=True)
    b = sorted([int(n) for n in input().split()], reverse=True)
    c = sorted([int(n) for n in input().split()], reverse=True)
    va = np.array(a)[:, np.newaxis, np.newaxis]
    vb = np.array(b)[np.newaxis, :, np.newaxis]
    vc = np.array(c)[np.newaxis, np.newaxis, :]
    vx = np.arange(1, x + 1)[:, np.newaxis, np.newaxis]
    vy = np.arange(1, y + 1)[np.newaxis, :, np.newaxis]
    vz = np.arange(1, z + 1)[np.newaxis, np.newaxis, :]
    print(*(sorted((va + vb + vc)[(vx * vy * vz) <= k], reverse=True))[:k], sep="\n")


main()


### FIXED CODE ###

import sys


def main():
    x, y, z, k = [int(n) for n in input().split()]
    va = sorted([int(n) for n in input().split()], reverse=True)
    vb = sorted([int(n) for n in input().split()], reverse=True)
    xy = min(x*y, k)
    vab = (sorted([a + b for a in va for b in vb], reverse=True))[:xy]
    vc = sorted([int(n) for n in input().split()], reverse=True)
    xyz = min(x*y*z, k)
    print(*((sorted([ab + c for ab in vab for c in vc], reverse=True))[:xyz]), sep="\n")


main()
def Search(pos):
  L[pos-1] = 1
  if pos not in R:
    R[pos] = set()
    R[pos].add(1)
    return
  for i in R[pos]:
    if L[i-1] == 0:
      Search(i)

N, M = map(int, input().split())
R = {}
for i in range(M):
  A, B = map(int, input().split())
  if A not in R:
    R[A] = set()
  if B not in R:
    R[B] = set()
  R[A].add(B)
  R[B].add(A)
L = [0] * N
ans = -1
while sum(L) < N:
  ans += 1
  Search(L.index(0) + 1)
print(ans) 

### FIXED CODE ###

N, M = map(int, input().split())
L = [0] * N
D = {}
c = 1
for i in range(M):
  A, B = map(int, input().split())
  if L[A - 1] == L[B - 1] == 0:
    D[c] = set()
    D[c].add(A)
    D[c].add(B)
    L[A - 1] = c
    L[B - 1] = c
    c += 1
  elif L[A - 1] == 0:
    D[L[B - 1]].add(A)
    L[A - 1] = L[B - 1]
  elif L[B - 1] == 0:
    D[L[A - 1]].add(B)
    L[B - 1] = L[A - 1]
  elif L[A - 1] != L[B - 1]:
    if len(D[L[A - 1]]) < len(D[L[B - 1]]):
      A, B = B, A
    D[L[A - 1]] |= D[L[B - 1]]
    for j in D.pop(L[B - 1]):
      L[j - 1] = L[A - 1]
  #print(L, D, sep = "\n")
print(len(D) + L.count(0) - 1)
n,m = map (int,input().split())
a = [0] * n
b = [0] * n
box = [[] for i in range(n)]
s = deque()
ans = [-1] * (n-1)
for i in range(n):
    a[i],b[i] = map (int,input().split())
    box[a[i]-1].append (b[i])
    box[b[i] - 1].append (a[i])
for i in range(len(box[0])):
    s.append([1,box[0][i]])

while len (s) > 0:
    k = s.popleft()

    if ans[k[1] - 2] == -1:
        ans[k[1] - 2] = k[0]

        for i in range(len(box[k[1] - 1])):
            s.append([k[1], box[k[1] - 1][i]])

print('Yes')
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque


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


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


def MI(): return map(int, sys.stdin.readline().rstrip().split())


def MS(): return map(str, sys.stdin.readline().rstrip().split())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def LS(): return list(sys.stdin.readline().rstrip().split())


# N = I()
# A = [LI() for _ in range(N)]


n, m = map(int, input().split())
a = [0] * m
b = [0] * m
box = [[] for i in range(n)]
s = deque()
ans = [-1] * (n - 1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    box[a[i] - 1].append(b[i])
    box[b[i] - 1].append(a[i])
for i in range(len(box[0])):
    s.append([1, box[0][i]])

while len(s) > 0:
    k = s.popleft()

    if ans[k[1] - 2] == -1 and k[1] - 2 != -1:
        ans[k[1] - 2] = k[0]

        for i in range(len(box[k[1] - 1])):
            s.append([k[1], box[k[1] - 1][i]])

print('Yes')
for i in range(len(ans)):
    print(ans[i])
# coding:utf-8


def main():
    A, B, K = map(int, input().split())
    ans = []

    for i in range(1, max(A, B)):
        if A % i == 0 and B % i == 0:
            ans.append(i)
        if len(ans) >= K:
            break
    # print(ans)
    print(ans[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding:utf-8


def main():
    A, B, K = map(int, input().split())
    ans = []
    ans.append(1)
    for i in range(2, max(A, B)+1):
        if A % i == 0 and B % i == 0:
            ans.append(i)
        # if len(ans) >= K:
        #     break
    # print(ans)
    print(ans[-K])


if __name__ == "__main__":
    main()
import math
    S = list(input())
    K = int(input())
    s = S * 2
    c1 = 0
    c2 = 0
    for i in range(len(s)-1):
        if s[i+1] == s[i]:
            if i < len(S)-1:
                c1 += 1
            c2 += 1
            s[i+1] = 0
    c = S[0]
    for s in S:
        if s != c:
            print(c1+(c2-c1)*(K-1))
            exit()
    print(math.floor(len(S)*K/2))

import math
S = list(input())
K = int(input())
s = S * 2
c1 = 0
c2 = 0
for i in range(len(s)-1):
    if s[i+1] == s[i]:
        if i < len(S)-1:
            c1 += 1
        c2 += 1
        s[i+1] = 0
c = S[0]
for s in S:
    if s != c:
        print(c1+(c2-c1)*(K-1))
        exit()
print(math.floor(len(S)*K/2))

### FIXED CODE ###

import math
S = list(input())
K = int(input())
s = S * 2
c1 = 0
c2 = 0
for i in range(len(s)-1):
    if s[i+1] == s[i]:
        if i < len(S)-1:
            c1 += 1
        c2 += 1
        s[i+1] = 0
c = S[0]
for s in S:
    if s != c:
        print(c1+(c2-c1)*(K-1))
        exit()
print(math.floor(len(S)*K/2))
s = input()
n = len(s)

a = [0]*2019
count = 0
val = 10
for i in range(n):
    tmp = int(s[n-i-1,n]) % 2019
    count = count + a[tmp]
    a[tmp] = a[tmp] + 1
    if(tmp == 0):
        count = count + 1
    val = val * 10

print(count)

### FIXED CODE ###

s = input()[::-1]
n = len(s)

a = [0]*2019
a[0] = 1
count = 0
val = 1
current = 0
for c in s:
    current = (current + val * int(c)) % 2019
    count += a[current%2019]
    a[current%2019] += 1
    val = val * 10 % 2019

print(count)
n, k = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
ans = 0

for i in range(k):
  ans += p[i]
  
print(ans)


### FIXED CODE ###

alpha = input()
print('A' if alpha.isupper() else 'a')
import sys
li = list(map(int,input().split()))
li.sort()
for i in range(3):
  if(str(li[i]) == str(li[i+1]) == str(li[i+2])):
    print("No")
    sys.exit()
  if(str(li[i]) == str(li[i+1])):
    print("Yes")
    break
else:
  print("No")

### FIXED CODE ###

import sys
li = list(map(int,input().split()))
li.sort()
if(str(li[0]) == str(li[1]) == str(li[2])):
  print("No")
  sys.exit()
if(str(li[0]) != str(li[1]) != str(li[2])):
  print("No")
  sys.exit()
for i in range(3):
  if(str(li[i]) == str(li[i+1])):
    print("Yes")
    break
from math import gcd
from functools import reduce

def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


def f():
    s = set()
    for i in range(N - 1, -1. -1):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


N, *A = map(int, open(0).read().split())

prime_table = make_prime_table(10 ** 6)
if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

from math import gcd
from functools import reduce

def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


def f():
    s = set()
    for i in range(N - 1, -1, -1):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


N, *A = map(int, open(0).read().split())

prime_table = make_prime_table(10 ** 6)
if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 21
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve(n=None, s1=None, s2=None):
    n, k = getList()
    pli = getList()
    cli = getList()

    ans = max(cli)
    for i in range(n):
        cycle = [i]
        pts = [cli[i]]
        pos = i
        while True:
            pos = pli[pos] - 1
            if pos != i:
                cycle.append(pos)
                pts.append(cli[pos])
            else:
                break
        lc = len(cycle)
        for j in range(lc - 1):
            pts[j+1] += pts[j]

        if k <= lc:
            tmp = max(pts[:k])
        else:
            each = k % lc
            rotate = k // lc
            if pts[-1] > 0:
                tmp = pts[-1] * rotate + max(pts[:each])
            else:
                tmp = max(pts)
        # print(tmp, sum(pts), pts)
        ans = max(ans, tmp)

    print(ans)


def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()



### FIXED CODE ###

import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 21
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve(n=None, s1=None, s2=None):
    n, k = getList()
    pli = getList()
    cli = getList()

    ans = max(cli)
    for i in range(n):
        cycle = [i]
        pts = [cli[i]]
        pos = i
        while True:
            pos = pli[pos] - 1
            if pos != i:
                cycle.append(pos)
                pts.append(cli[pos])
            else:
                break
        lc = len(cycle)
        acc = 0
        sumpts = sum(pts)
        for j in range(lc):
            acc += pts[j]

            if sumpts > 0:
                around = (k - j - 1) // lc
                tmp = acc + sumpts * around
            else:
                tmp = acc
            ans = max(ans, tmp)

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()
a,b,c=int(input().split());print(min(a*b,c))

### FIXED CODE ###

a,b,c=map(int,input().split());print(min(a*b,c))
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from random import randint

    def score(t):
        memo = [0] * 26
        ans = 0
        for i, tt in enumerate(t):
            ans += s[i][tt - 1]
            memo[tt - 1] = i + 1
            for m, cc in zip(memo, c):
                ans -= cc * (i + 1 - m)
        return ans

    d = int(readline())
    c = list(map(int, readline().split()))
    s = [list(map(int, readline().split())) for _ in range(d)]
    t = [0] * d
    r = [0] * d
    check = 0
    for i in range(d):
        t[i] = s[i].index(max(s[i])) + 1
        check = score(t)
    for i in range(10 ** 4):
        for j in range(d):
            r[j] = randint(1, d)
        if check < score(r):
            t = r
    print('\n'.join(map(str, t)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    d = int(readline())
    c = list(map(int, readline().split()))
    s = [list(map(int, readline().split())) for _ in range(d)]
    for i in range(d):
        print(s[i].index(max(s[i])) + 1)


if __name__ == '__main__':
    main()
inp = input().split()
l = int(inp[0])
r = int(inp[1])

int_list_pre = list(range(l,r+1))
int_list = [s%2019 for s in int_list_pre]
print(int_list)
l = len(int_list)
min_mod = 2018

for i in range(l):
    for j in range(l):
        if j > i:
            compare = (int_list[i] * int_list[j])%2019
            if compare < min_mod:
                min_mod = compare


print(min_mod)


### FIXED CODE ###

inp = input().split()
l = int(inp[0])
r = int(inp[1])

if r - l > 2019:
    print(0)
else:
    int_list_pre = list(range(l,r+1))
    int_list = [s%2019 for s in int_list_pre]
    l_l = len(int_list)
    min_mod = 2018

    for i in range(l_l):
        for j in range(l_l):
            if j > i:
                compare = (int_list[i] * int_list[j])%2019
                if compare < min_mod:
                    min_mod = compare


    print(min_mod)
N=int(input())
s=[int(input()) for _ in range(N)]
M=int(input())
t=[int(input()) for _ in range(M)]
l=list(set(N))
print(max(0,max(s.count(l[i])-t.count(l[i]) for i in range(len(l)))))

### FIXED CODE ###

N=int(input())
s=[input() for _ in range(N)]
M=int(input())
t=[input() for _ in range(M)]
l=list(set(s))
print(max(0,max(s.count(l[i])-t.count(l[i]) for i in range(len(l)))))
n = input()

x = False

while x = False:
  for i in range(1,len(n)):
    if n[i-1] == n[i]:
      x =True
    else:
      x = False
  if x = True:
    print(n)
    break
  else:
    n = int(n) + 1

### FIXED CODE ###

n=int(input())
for i in range(10):
  if 111*i<n<=111*(i+1):
    print(111*(i+1))
s, w = map(int, input().split())
print("safe" s > w else "unsafe")

### FIXED CODE ###

s, w = map(int, input().split())
print("safe" if s > w else "unsafe")
a,b,c = map(int,input().split())
if a < b and b < c :
	print('Yes')
else
	print('No')
  


### FIXED CODE ###

a,b,c = map(int,input().split())
if a < b and b < c :
	print('Yes')
else:
	print('No')
S, T = map(input().split())
print(T+S)

### FIXED CODE ###

S, T = input().split()
print(T+S)
import math
a,b,c = map(float,input().split())
print("Yes" if a**0.5+b**0.5 < c**0.5 and math.isclose(a**0.5+b**0.5 , c**0.5)==False else "No")


### FIXED CODE ###

from decimal import Decimal
a,b,c = map(float,input().split())
print("Yes" if Decimal(a)**Decimal(0.5)+Decimal(b)**Decimal(0.5) < Decimal(c)**Decimal(0.5) else "No")
n, w = map(int, input().split())

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

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*(num) for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(num):
        if v + nap[i][1] <= num:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(num)):
    if dp[n][v] <= w:
        print(v)
        exit()


### FIXED CODE ###

n, w = map(int, input().split())

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

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*(10**5+10) for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(10**5+1):
        if v + nap[i][1] <= 10**5+1:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(10**5+1)):
    if dp[n][v] <= w:
        print(v)
        exit()
N,M = map(int, input().split())
ans = 0
while not (n == 0 and m == 0):
 for i in range(N):
  for j in range(N):
   for k in range(N):
    if ( i==j or i==k or j==k):
    elif(i + j + k == M): ans += 1
print(ans)

### FIXED CODE ###

N,M = map(int, input().split())
ans = 0
while not (N == 0 and M == 0):
 for i in range(1, N+1):
  for j in range(i+1, N+1):
   k = M - i - j
   if ( k > N): pass
   elif  k <= j : break
   else: ans += 1
 print(ans)
 ans = 0
 N,M = map(int, input().split())
s=input()
print(700+100*lsit(s).count('o'))

#組み込み関数というやつ？シンプルだけど覚えること多そう

### FIXED CODE ###

s=input()
print(700+100*list(s).count('o'))
import sys
input = sys.stdin.readline
import math
import time
import numpy as np

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

k = int(input())


a = prime_factorize(k)

def nana(n):
    for i in range(1,100000):
        na = int("7"*i)
        if na % n ==0:
            return i

if k %2 == 0:
    print(-1)
else:
    t = []
    for e in a:
        t.append(nana(e))
    print(np.gcd.reduce(t))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math
import time
import numpy as np

k = int(input())

if k %2 ==0 or k%5==0:
    print(-1)
else:
    if k %7 == 0:
        l = k*9//7
    else:
        l = k*9
    q = 10%l
    for i in range(1,1000000):
        if q ==1:
            print(i)
            break
        else:
            q = (q*10)%l
            pass
import math
a,b=[int(i) for i in input().split()]
#def lcm(x,y):
    #return (x*y) // math.gcd(x,y)

  
  
z= (a*b) // math.gcd(a,b)
print(z)

### FIXED CODE ###

A, B=[int(i) for i in input().split()]

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
  
print(lcm(A,B))
from sys import stdin
from decimal import Decimal
N = int(stdin.readline().rstrip())
A = []
B = []
for i in range(N):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    A.append(a)
    B.append(b)
    
A.sort()
B.sort()
if N % 2 == 0:
    C = A+B
    C.sort()
    ans = 2 * sum(C[::-1][:N]) - 2 * sum(C[:N])
    print(ans//2+1)
else:
    ans = B[N//2] - A[N//2] + 1
    print(ans

### FIXED CODE ###

from sys import stdin
from decimal import Decimal
N = int(stdin.readline().rstrip())
A = []
B = []
for i in range(N):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    A.append(a)
    B.append(b)
    
A.sort()
B.sort()

if N % 2 == 0:
    n = N // 2
    med1 = A[n-1] + A[n]
    med2 = B[n-1] + B[n]
    print(med2-med1+1)
else:
    ans = B[N//2] - A[N//2] + 1
    print(ans)
n=int(input())
for i in range(n):
	rest=list(input().split())
a=rest
rest.sort()
for i in range(n):
	print(rest.index(a[i])
		

### FIXED CODE ###

from collections import defaultdict
n=int(input())

rest=defaultdict(list)
for i in range(n):
	s,h=input().split()
	rest[s].append([int(h),i+1])
for k in sorted(list(rest.keys())):
	for p,i in sorted(list(rest[k]),key=lambda x:x[0])[::-1]:
		print(i)
from functools import reduce

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

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

def lcm_base(a, b):
  return a * b / gcd(a, b)

def lcm(n):
  return reduce(lcm_base, n)

f = 0
for i in a:
  f += (lcm(a) - 1) % i

print(int(f))


### FIXED CODE ###

n = int(input())
print(sum(list(map(int, input().split()))) - n)
import math
x = 0
y = 0
r = 90
while True:
    d,t=map(int, input().split())
    if d==0 and t==0:
        print(int(x),int(y),sep='\n')
        exit()
    x += math.cos(math.radians(r)) * d
    y += math.sin(math.radians(r)) * d
    r -= t

### FIXED CODE ###

import math
x = 0
y = 0
r = 90
while True:
    d,t=map(int, input().split(','))
    if d==0 and t==0:
        print(int(x),int(y),sep='\n')
        exit()
    x += math.cos(math.radians(r)) * d
    y += math.sin(math.radians(r)) * d
    r -= t