배씨는 신나게 도로를 달리는 중이다. 도로는 정확히 100km 이고, 배씨는 무조건 도로의 끝까지 달려야한다.

도로의 각 구간에는 제한속도를 지정해 두었으나 배씨는 속도 위반에는 개의치 않아 자신이 원하는 속도로 달린다.

도로는 N개의 구간으로 나뉘며 각 구간에는 도로 길이와 해당 도로의 제한속도가 주어진다.

도로 N개의 총 합은 100km 이며 각 구간별 도로 길이와 제한 속도는 모두 양의 정수이다.

예를 들어, N이 3이고 (40, 75), (50, 35), (10, 45) 이라면

배씨가 달린 도로 또한 M 개 구간으로 나뉘며 각 구간에는 도로 길이와 배씨가 달린 속도가 주어진다.

M 개의 도로 총 합은 100km 이며 각 구간별 도로 길이와 달린 속도는 모두 양의 정수이다.

예를 들어 M 이 3이고 (40, 76), (20, 30), (40, 40) 이라면

배씨가 100km 도로를 달리는 동안 속도를 위반한 최댓값을 구하시오.

속도 위반 단속 timer 2초 memory 512MB

속도 위반 단속 2초 512MB