Softeer: GBC

O(N) algorithm

import sys
import bisect

limits = []
test = []

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

for i in range(N):
    limits += list(map(int, sys.stdin.readline().split())),

for i in range(M):
    test += list(map(int, sys.stdin.readline().split())),


for i in range(len(limits) - 1):
    limits[i + 1][0] += limits[i][0]

for i in range(len(test) - 1):
    test[i + 1][0] += test[i][0]

mx = 0
for end, speed in test:
    while limits and limits[0][0] < end:
        if speed > limits[0][1]:
            mx = max(speed - limits[0][1], mx)
        limits.pop(0)

    if limits and end <= limits[0][0]:
        if speed > limits[0][1]:
            mx = max(speed - limits[0][1], mx)

    if limits and limits[0][0] == end:
        limits.pop(0)

print(mx)