시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 91 54 49 62.821%

문제

말썽꾸러기 연정이는 오늘도 태우의 자동차를 몰래타고 신나게 도로를 달리는 중이다.

도로는 정확히 100km 이며 연정이는 무조건 도로의 끝까지 달려야한다.

도로의 각 구간에는 제한속도를 지정해 두었으나 쿨한 연정이는 속도 위반에는 개의치 않아 (더군다나 자신의 차도 아니므로) 자신이 원하는 속도로 달린다.

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

N 개의 도로 총 합은 100km 이며 각 구간별 도로 길이와 제한 속도는 모두 양의 정수이다. 예를 들어 N 이 3 이고 (40 , 75) , (50 , 35) , (10 , 45) 이라면 

  • 첫 구간의 도로 길이는 40km , 제한속도는 75km/h 
  • 두 번째 구간의 도로 길이는 50km , 제한 속도는 35km/h 
  • 세 번째 구간의 도로 길이는 10km , 제한 속도는 45km/h

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

M 개의 도로 총 합은 100km 이며 각 구간별 도로 길이와 달린 속도는 모두 양의 정수이다. 예를 들어 M 이 3이고 (40 , 76) , (20 , 30) , (40 , 40) 이라면 

  • 첫 구간에서 연정이가 달린 도로 길이는 40km , 달린 속도는 76km/h
  • 두 번째 구간에서 달린 도로 길이는 20km , 달린 속도는 30km/h
  • 세 번째 구간에서 달린 도로 길이는 40km , 달린 속도는 40km/h

연정이가 100km 도로를 달리는 동안 속도를 위반한 최대값을 구하시오.

입력

첫 줄은 N , M 이 주어진다.

그 다음줄 부터 N 줄은 각 구간의 길이 및 해당 구간에서의 제한 속도가 주어지며

그 다음 M 줄은 연정이가 달린 각 구간의 길이와해당 구간에서 달린 속도가 주어진다.

출력

연정이가 도로를 달리는 동안 속도 위반한 최대값을 출력하시오. ( 단 , 속도 위반을 하지 않았다면 0을 출력하시오. )

예제 입력

3 3
40 75
50 35
10 45
40 76
20 30
40 40

예제 출력

5

힌트

예를 들어 도로가 3구역 [ ( 40km , 75km/h ) ,  ( 50km , 35km/h ) ,  ( 10km , 45km/h )  ] 이고 

연정이가 달린 3구역 [ ( 40km , 76km/h ) ,  ( 20km , 30km/h ) ,  ( 40km , 40km/h ) ] 이라면 

처음 0 ~ 40km 영역에서 1km/h 만큼 위반했으나 40km ~ 90km 사이에서 5km/h 만큼 위반했기에 연정이가 위반한 최대 값은 5 이다.