Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    M = int(input())
    wa = 0
    ans = 0
    for _ in range(M):
        d, c = [int(x) for x in input().split()]
        for _ in range(c):
            wa += d
            ans += 1
            if wa >= 10:
                ans += 1
                wa = wa % 10 + 1
    
    print(ans - 1)

    



if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline

def main():
    M = int(input())
    count = 0
    wa = 0
    for _ in range(M):
        d, c = [int(x) for x in input().split()]
        count += c
        wa += d * c
    
    print(count - 1 + ((wa - 1) // 9))
    



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    M = int(input())
    wa = 0
    ans = 0
    for _ in range(M):
        d, c = [int(x) for x in input().split()]
        for _ in range(c):
            wa += d
            ans += 1
            if wa >= 10:
                ans += 1
                wa = wa % 10 + 1
    
    print(ans - 1)

    



if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline

def main():
    M = int(input())
    count = 0
    wa = 0
    for _ in range(M):
        d, c = [int(x) for x in input().split()]
        count += c
        wa += d * c
    
    print(count - 1 + ((wa - 1) // 9))
    



if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import math

def main():
    a, b, x = [int(x) for x in input().split()]
    b_now = x / (a * a)
    menseki = b_now * a
    ans_a = menseki * 2 / b

    if ans_a <= a:
        z = math.degrees(math.atan(ans_a / b))
        print(90 - z)
        exit()
    else:
        menseki = a * b - menseki
        ans_b = menseki * 2 / a
        z = math.degrees(math.atan(a / ans_b))
        print(90 - z)
        exit()



if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline
import math

def main():
    a, b, x = [int(x) for x in input().split()]
    b_now = x / (a * a)
    menseki = b_now * a
    ans_a = menseki * 2 / b

    if a * a * b == x:
        print(0)
        exit()

    if ans_a <= a:
        z = math.degrees(math.atan(ans_a / b))
        print(90 - z)
        exit()
    else:
        menseki = a * b - menseki
        ans_b = menseki * 2 / a
        z = math.degrees(math.atan(a / ans_b))
        print(90 - z)
        exit()



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import math

def main():
    a, b, x = [int(x) for x in input().split()]
    b_now = x / (a * a)
    menseki = b_now * a
    ans_a = menseki * 2 / b

    # 三角形の場合
    if ans_a <= a:
        z = math.degrees(math.atan(ans_a / b))
        print(90 - z)
        exit()

    # 三角形 + 平行四辺形の場合
    else:
        menseki = a * b - menseki
        ans_b = menseki * 2 / a
        z = math.degrees(math.atan(a / ans_b))
        print(90 - z)
        exit()



if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline
import math

def main():
    a, b, x = [int(x) for x in input().split()]
    b_now = x / (a * a)
    menseki = b_now * a
    ans_a = menseki * 2 / b

    if a * a * b == x:
        print(0)
        exit()

    if ans_a <= a:
        z = math.degrees(math.atan(ans_a / b))
        print(90 - z)
        exit()
    else:
        menseki = a * b - menseki
        ans_b = menseki * 2 / a
        z = math.degrees(math.atan(a / ans_b))
        print(90 - z)
        exit()



if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import heapq

def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    F = [int(x) for x in input().split()]

    A_s = sorted(A, reverse=True)
    F_s = sorted(F)
    C = []
    C_h = []
    for i in range(N):
        x = A_s[i] * F_s[i]
        C.append(x)
        heapq.heappush(C_h, -x)

    for _ in range(K):
        x = -heapq.heappop(C_h)
        i = C.index(x)
        A_s[i] -= 1
        y = A_s[i] * F_s[i]
        C[i] = y
        heapq.heappush(C_h, -y)

    x = -heapq.heappop(C_h)
    print(x)











if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline

def check(A, F, mid, k):
    for i in range(len(A)):
        if A[i] * F[i] > mid:
            x = A[i] - mid // F[i]
            k -= x
        if k < 0:
            return False
    return True



def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    F = [int(x) for x in input().split()]

    A_s = sorted(A, reverse=True)
    F_s = sorted(F)

    l = -1
    r = 10 ** 13
    while r - l != 1:
        mid = (r + l) // 2
        if check(A_s, F_s, mid, K):
            r = mid
        else:
            l = mid

    print(r)











if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import heapq

def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    F = [int(x) for x in input().split()]

    A_s = sorted(A, reverse=True)
    F_s = sorted(F)
    C = []
    C_h = []
    for i in range(N):
        x = A_s[i] * F_s[i]
        C.append(x)
        heapq.heappush(C_h, -x)

    for _ in range(K):
        x = -heapq.heappop(C_h)
        i = C.index(x)
        A_s[i] -= 1
        y = A_s[i] * F_s[i]
        C[i] = y
        heapq.heappush(C_h, -y)

    x = -heapq.heappop(C_h)
    print(x)











if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline

def check(A, F, mid, k):
    for i in range(len(A)):
        if A[i] * F[i] > mid:
            x = A[i] - mid // F[i]
            k -= x
        if k < 0:
            return False
    return True



def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    F = [int(x) for x in input().split()]

    A_s = sorted(A, reverse=True)
    F_s = sorted(F)

    l = -1
    r = 10 ** 13
    while r - l != 1:
        mid = (r + l) // 2
        if check(A_s, F_s, mid, K):
            r = mid
        else:
            l = mid

    print(r)











if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    A = []
    C = []
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        c = [int(x) for x in input().split()]
        tmp = 0
        for cc in c:
            tmp |= 1 << (cc - 1)

        C.append(tmp)

    dp = [float("inf")] * (2 ** N + 1)

    dp[0] = 0

    for i in range(M):
        for k in range(2 ** N + 1):
            next = C[i] | k
            if next >= (2 ** N + 1):
                continue
            dp[next] = min(dp[next], dp[k] + A[i])

    if dp[2 ** N - 1] == float("inf"):
        print(-1)
    else:
        print(dp[2 ** N - 1])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    A = []
    C = []
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        c = [int(x) for x in input().split()]
        tmp = 0
        for cc in c:
            tmp |= 1 << (cc - 1)

        C.append(tmp)

    dp = [float("inf")] * (2 ** N + 1)

    dp[0] = 0

    for i in range(M):
        for k in range(2 ** N + 1):
            next = C[i] | k
            if next >= (2 ** N + 1):
                continue
            dp[next] = min(dp[next], dp[k] + A[i])

    if dp[2 ** N - 1] == float("inf"):
        print(-1)
    else:
        print(dp[2 ** N - 1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
print(sum(range(1, N)))

Fixed submission:
S = input()
T = input()
count = 0
for x in range(len(S)):
    if S[x] == T[x]:
        count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
print(sum(range(1, N)))

Fixed submission:
N = int(input())
print(sum(range(1, N)))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
N_array = [x for x in range(1, N + 1, 1)]
N_array.pop(N - 1)
print(sum(N_array))

Fixed submission:
N = int(input())
print(sum(range(1, N)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

s = input()
t = input()

including = True
for x in t:
    if x  not in s:
        including = False
        break
if not including:
    print(-1)
    sys.exit()


x = 0
y = 0
while True:
    index = x % len(s)
    if s[index] == t[y]:
        y += 1
        if y == len(t):
            break
    x += 1

print(x + 1)

Fixed submission:
import bisect

S = input().strip()
T = input().strip()

x = [[] for j in range(26)]

for i, s in enumerate(S):
    x[ord(s) - ord('a')].append(i)

sett = list(set(T))

for t in sett:
    if len(x[ord(t) - ord('a')]) == 0:
        print(-1)
        exit()

c = 0
z = 0

for t in T:
    y = bisect.bisect_left(x[ord(t) - ord('a')], c)
    if y == len(x[ord(t) - ord('a')]):
        z += 1
        c = x[ord(t) - ord('a')][0] + 1
    else:
        c = x[ord(t) - ord('a')][y] + 1

print(z * len(S) + c)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

s = input()
t = input()

including = True
for x in t:
    if x  not in s:
        including = False
        break
if not including:
    print(-1)
    sys.exit()


x = 0
y = 0
while True:
    index = x % len(s)
    if s[index] == t[y]:
        y += 1
        if y == len(t):
            break
    x += 1

print(x + 1)

Fixed submission:
import bisect

S = input().strip()
T = input().strip()

x = [[] for j in range(26)]

for i, s in enumerate(S):
    x[ord(s) - ord('a')].append(i)

sett = list(set(T))

for t in sett:
    if len(x[ord(t) - ord('a')]) == 0:
        print(-1)
        exit()

c = 0
z = 0

for t in T:
    y = bisect.bisect_left(x[ord(t) - ord('a')], c)
    if y == len(x[ord(t) - ord('a')]):
        z += 1
        c = x[ord(t) - ord('a')][0] + 1
    else:
        c = x[ord(t) - ord('a')][y] + 1

print(z * len(S) + c)

Buggy python submission (verdict: Runtime Error):
s = input()
t = input()

including = True
for x in t:
    if x  not in s:
        including = False
        break
if not including:
    print(-1)
    return


x = 0
y = 0
while True:
    index = x % len(s)
    if s[index] == t[y]:
        y += 1
        if y == len(t):
            break
    x += 1

print(x + 1)

Fixed submission:
import bisect

S = input().strip()
T = input().strip()

x = [[] for j in range(26)]

for i, s in enumerate(S):
    x[ord(s) - ord('a')].append(i)

sett = list(set(T))

for t in sett:
    if len(x[ord(t) - ord('a')]) == 0:
        print(-1)
        exit()

c = 0
z = 0

for t in T:
    y = bisect.bisect_left(x[ord(t) - ord('a')], c)
    if y == len(x[ord(t) - ord('a')]):
        z += 1
        c = x[ord(t) - ord('a')][0] + 1
    else:
        c = x[ord(t) - ord('a')][y] + 1

print(z * len(S) + c)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

N = int(input())
s = []
for _ in range(N):
    s_array = sorted(input())
    x = ""
    for i in s_array:
        x += i
    s.append(x)


count = 0
for x in range(N):
    for y in range(x + 1, N):
        if s[x] == s[y]:
            count += 1
print(count)

Fixed submission:
import sys
input=sys.stdin.readline

N = int(input())
hash = {}
count = 0
for _ in range(N):
    x = "".join(sorted(input()))
    if x in hash:
        count += hash[x]
    else:
        hash[x] = 0
    hash[x] += 1

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

N = int(input())
s = []
for _ in range(N):
    s.append(sorted(input()))

count = 0
for x in range(N):
    for y in range(x + 1, N):
        if s[x] == s[y]:
            count += 1
print(count)

Fixed submission:
import sys
input=sys.stdin.readline

N = int(input())
hash = {}
count = 0
for _ in range(N):
    x = "".join(sorted(input()))
    if x in hash:
        count += hash[x]
    else:
        hash[x] = 0
    hash[x] += 1

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

N = int(input())
s = []
for _ in range(N):
    s.append(sorted(input()))

count = 0
for x in range(N):
    for y in range(x + 1, N):
        if s[x] == s[y]:
            count += 1
print(count)

Fixed submission:
import sys
input=sys.stdin.readline

N = int(input())
hash = {}
count = 0
for _ in range(N):
    x = "".join(sorted(input()))
    if x in hash:
        count += hash[x]
    else:
        hash[x] = 0
    hash[x] += 1

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

N = int(input())
s = []
for _ in range(N):
    s.append(sorted(input()))

count = 0
for x in range(N):
    for y in range(x + 1, N):
        if s[x] == s[y]:
            count += 1
print(count)

Fixed submission:
import sys
input=sys.stdin.readline

N = int(input())
hash = {}
count = 0
for _ in range(N):
    x = "".join(sorted(input()))
    if x in hash:
        count += hash[x]
    else:
        hash[x] = 0
    hash[x] += 1

print(count)
Buggy python submission (verdict: Runtime Error):
N = int(input().rstrip())
A = []
for _ in range(N):
    A.append(int(input().rstrip()))

max_num = max(A)

for i in range(N):
    if A[i] != max_num:
        print(max_num)
    else:
        if i == N - 1:
            print(max(A[0:i]))
        else:
            print(max(max(A[0:i]),max(A[i + 1:])))


Fixed submission:
N = int(input().rstrip())
A = []
for _ in range(N):
    A.append(int(input().rstrip()))

A_sorted = sorted(A)

for i in range(N):
    if A[i] != A_sorted[-1]:
        print(A_sorted[-1])
    else:
        print(A_sorted[-2])

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

max_num = max(A)

for i in range(N):
    if A[i] != max_num:
        print(max_num)
    else:
        print(max(max(A[0:i]),max(A[i + 1:])))
    



Fixed submission:
N = int(input().rstrip())
A = []
for _ in range(N):
    A.append(int(input().rstrip()))

A_sorted = sorted(A)

for i in range(N):
    if A[i] != A_sorted[-1]:
        print(A_sorted[-1])
    else:
        print(A_sorted[-2])

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

max_num = max(A)

for i in range(N):
    if A[i] != max_num:
        print(max_num)
    else:
        print(max(max(A[0:i]),max(A[i + 1:]))
    



Fixed submission:
N = int(input().rstrip())
A = []
for _ in range(N):
    A.append(int(input().rstrip()))

A_sorted = sorted(A)

for i in range(N):
    if A[i] != A_sorted[-1]:
        print(A_sorted[-1])
    else:
        print(A_sorted[-2])
Buggy python submission (verdict: Time Limit Exceeded):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


N = int(input())
A = [int(x) for x in input().split()]
ans = []
score = [0] * N

for i in range(N - 1, -1, -1):
    if score[i] % 2 != A[i]:
        ans.append(i + 1)
        divisors = make_divisors(i + 1)
        for v in divisors:
            score[v - 1] += 1



print(len(ans))
if len(ans) != 0:
    for v in ans:
        print(v, end=" ")

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


N = int(input())
A = [int(x) for x in input().split()]
ans = []
score = [0] * N

for i in range(N - 1, -1, -1):
    if score[i] % 2 != A[i]:
        ans.append(i + 1)
        divisors = make_divisors(i + 1)
        for v in divisors:
            score[v - 1] += 1



print(len(ans))
if len(ans) != 0:
    for v in ans:
        print(v, end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]

x = []

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.insert(0, a)
        else:
            x[r - 1] = a

print(len(x))


Fixed submission:
import bisect
import  collections

N = int(input())
A = [int(input()) for _ in range(N)]

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

x = []

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = len(x) - 1
        l = 0
        while r - l != 1 and r - l != 0:
            m = (r + l) // 2
            if a > x[m]:
                l = m
            else:
                r = m

        if a > x[r]:
            x[r] = a
        elif a > x[l]:
            x[l] = a
        else:
            x.append(a)
        x.sort()

print(len(x))


Fixed submission:
import bisect
import  collections

N = int(input())
A = [int(input()) for _ in range(N)]

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

color = []
for i in range(N):
    if i == 0:
        color.append(A[i])
    else:
        for j in range(len(color)):
            if A[i] > color[j]:
                color[j] = A[i]
                break
        else:
            color.append(A[i])

print(len(color))




Fixed submission:
import bisect
import  collections

N = int(input())
A = [int(input()) for _ in range(N)]

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))
Buggy python submission (verdict: Time Limit Exceeded):
L, R = [int(x) for x in input().split()]

min = 1000000000000000000000000000

for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        if min > i * j % 2019:
            min = i * j % 2019
        if min == 0:
            break

print(min)



Fixed submission:
L, R = [int(x) for x in input().split()]

min = 1000000000000000000000000000

if R - L > 2019:
    print(0)
    exit()

for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        if min > i * j % 2019:
            min = i * j % 2019
        if min == 0:
            break

print(min)
Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = [int(x) for x in input().split()]

X = (C * D) // math.gcd(C, D)
ans = (B - A + 1)\
      - (B // C - A // C)\
      - (B // D - A // D)\
      + (B // X - A // X)
if A % C == 0:
      ans -= 1
if A % D == 0:
      ans -= 1
if A % X == 0:
      ans += 1

print(ans)


Fixed submission:
import fractions

A, B, C, D = [int(x) for x in input().split()]

X = (C * D) // fractions.gcd(C, D)
ans = (B - A + 1)\
      - (B // C - A // C)\
      - (B // D - A // D)\
      + (B // X - A // X)
if A % C == 0:
      ans -= 1
if A % D == 0:
      ans -= 1
if A % X == 0:
      ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    XY = [[int(x) for x in input().split()] for _ in range(N)]

    c = collections.Counter()

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            xi, yi = XY[i]
            xj, yj = XY[j]
            c[(xi - xj, yi - yj)] += 1

    print(N - c.most_common()[0][1])


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    XY = [[int(x) for x in input().split()] for _ in range(N)]

    c = collections.Counter()

    if N == 1:
        print(1)
        return

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            xi, yi = XY[i]
            xj, yj = XY[j]
            c[(xi - xj, yi - yj)] += 1

    print(N - c.most_common()[0][1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
H, W = [int(x) for x in input().split()]

S = []
for _ in range(H):
    S.append(input())

TATE = [[0 for i in range(W + 1)] for j in range(H + 1)]
YOKO = [[0 for i in range(W + 1)] for j in range(H + 1)]


for j in range(1, H + 1):
    for i in range(1, W + 1):
        if S[j - 1][i - 1] == '.':
            YOKO[j][i] = YOKO[j][i - 1] + 1
        if S[j - 1][i - 1] == '.':
            TATE[j][i] = TATE[j - 1][i] + 1


for j in range(H, 0, -1):
    for i in range(W, 0, -1):
        if i != W and YOKO[j][i + 1] != 0 and S[j - 1][i - 1] == '.':
            YOKO[j][i] = YOKO[j][i + 1]
        if j != H and TATE[j + 1][i] != 0 and S[j - 1][i - 1] == '.':
            TATE[j][i] = TATE[j + 1][i]
ans = 0
for j in range(1, H + 1):
    for i in range(1, W + 1):
        ans = max(ans, TATE[j][i] + YOKO[j][i] - 1)

print(ans)








Fixed submission:
H, W = [int(x) for x in input().split()]

S = []
for _ in range(H):
    S.append(input())

TATE = [[0 for i in range(W + 1)] for j in range(H + 1)]
YOKO = [[0 for i in range(W + 1)] for j in range(H + 1)]


for j in range(1, H + 1):
    for i in range(1, W + 1):
        if S[j - 1][i - 1] == '.':
            YOKO[j][i] = YOKO[j][i - 1] + 1
        if S[j - 1][i - 1] == '.':
            TATE[j][i] = TATE[j - 1][i] + 1


for j in range(H, 0, -1):
    for i in range(W, 0, -1):
        if i != W and YOKO[j][i + 1] != 0 and S[j - 1][i - 1] == '.':
            YOKO[j][i] = YOKO[j][i + 1]
        if j != H and TATE[j + 1][i] != 0 and S[j - 1][i - 1] == '.':
            TATE[j][i] = TATE[j + 1][i]
ans = 0
for j in range(1, H + 1):
    for i in range(1, W + 1):
        ans = max(ans, TATE[j][i] + YOKO[j][i] - 1)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N, M = [int(x) for x in input().split()]

    answer = set()
    for i in range(M):
        L, R = [int(x) for x in input().split()]
        if i == 0:
            answer = {x for x in range(L, R + 1)}
        else:
            s = {x for x in range(L, R + 1)}
            answer &= s

    print(len(answer))




if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N, M = [int(x) for x in input().split()]

    A = []
    for i in range(M):
        A.append([int(x) for x in input().split()])

    answer = A[0]
    for i in range(1, M):
        if max(answer) < min(A[i]) or max(A[i]) < min(answer):
            print(0)
            exit()

        total = []
        total.extend(answer)
        total.extend(A[i])
        s_total = sorted(total)
        answer = s_total[1:3]

    print(answer[1] - answer[0] + 1)




if __name__ == '__main__':
    main()