속도 위반
면접 대비시간 제한2초메모리 제한512 MB
같은 100km 도로에 구간이 다르게 나뉜 제한속도와 주행속도를 비교해 초과량이 가장 큰 값을 구합니다.
문제
연정이는 태우의 차를 몰래 빌려 도로를 달린다. 도로 길이는 정확히 100km이고, 연정이는 끝까지 달린다. 제한 속도는 신경 쓰지 않고 원하는 속도로 달린다.
도로는 N개의 구간으로 나뉜다. 각 구간마다 구간의 길이와 그 구간의 제한 속도가 주어진다. N개 구간의 길이 합은 100km이고, 각 구간의 길이와 제한 속도는 모두 양의 정수다. 예를 들어 N이 3이고 구간이 순서대로 (40, 75), (50, 35), (10, 45)라면 첫 구간은 길이 40km에 제한 속도 75km/h, 둘째 구간은 길이 50km에 제한 속도 35km/h, 셋째 구간은 길이 10km에 제한 속도 45km/h다.
연정이가 달린 기록도 M개의 구간으로 나뉜다. 각 구간마다 구간의 길이와 그 구간에서 달린 속도가 주어진다. M개 구간의 길이 합도 100km이고, 각 구간의 길이와 달린 속도는 모두 양의 정수다.
두 분할의 경계는 서로 다를 수 있다. 도로 위 한 지점에서 위반한 양은 그 지점에서 달린 속도에서 그 지점의 제한 속도를 뺀 값이고, 이 값이 0 이하면 위반이 아니다. 연정이가 100km를 달리는 동안 위반한 양의 최댓값을 구하라.
입력
첫째 줄에 N과 M이 주어진다. 이어지는 N개의 줄에는 제한 속도 구간의 길이와 그 구간의 제한 속도가 한 줄에 하나씩 주어진다. 그다음 M개의 줄에는 연정이가 달린 구간의 길이와 그 구간에서 달린 속도가 한 줄에 하나씩 주어진다.
모든 값은 양의 정수이고, 두 분할 모두 길이의 합은 100이다. 길이가 양의 정수이므로 N과 M은 100 이하다.
출력
연정이가 위반한 양의 최댓값을 한 줄에 출력한다. 한 번도 위반하지 않았다면 0을 출력한다.
힌트
제한 속도 구간이 (40, 75), (50, 35), (10, 45)이고 달린 구간이 (40, 76), (20, 30), (40, 40)이라고 하자. 0km부터 40km까지는 76km/h로 달려 1km/h 초과했고, 60km부터 90km까지는 40km/h로 달려 5km/h 초과했다. 나머지 구간에서는 제한 속도를 넘지 않았으므로 답은 5다.