인터넷 업로드

해냈다! 당신은 대사관에 잠입해 정보원이 알려준 파일을 복사하는 데 성공했다. 힘겨운 탈출 끝에, 당국은 당신이 무슨 짓을 했는지 알아차리고 도시를 봉쇄했다. 그들이 당신을 잡기 전에 데이터를 인터넷에 업로드해야 한다.

다행히 도시에는 무료 wifi를 제공하는 커피숍이 많고, 당신은 작전을 시작하기 전에 그 정보를 조사해 두었다. 유일한 단점은 영업시간이 이상하고, 커피숍 사이를 이동해야 할 수도 있다는 것이다. 커피숍 사이를 이동하는 동안에는 데이터를 전혀 업로드할 수 없다.

커피숍 목록과 각 커피숍의 영업시간, wifi 속도가 주어질 때, 모든 데이터를 업로드할 수 있는 가장 이른 시각은 언제인가?

• 첫째 줄에는 데이터의 크기 d (1 ≤ d ≤ 109)가 메가바이트 단위로 주어진다.

• 둘째 줄에는 카페의 수 n (1 ≤ n ≤ 100)이 주어진다.

• 다음 n개 줄에는 각각 다음이 주어진다.

  • 카페의 영업 시작 시각과 종료 시각 o, c (0 ≤ o ≤ c ≤ 24 ∗ 60 ∗ 60)가 초 단위로 주어진다.
  • 카페의 wifi 속도 w (1 ≤ c ≤ 1000)가 초당 메가바이트 단위로 주어진다.

• n개 줄에 걸쳐, n번째 카페에서 각 카페로 이동하는 데 걸리는 시간이 초 단위로 주어진다 (0 ≤ di ≤ 24 ∗ 60 ∗ 60).

아무 카페에서나 그 카페가 문을 여는 순간 시작할 수 있고, 카페에 도착하는 즉시 wifi를 사용할 수 있다.

모든 데이터를 업로드할 수 있는 가장 작은 정수 시각을 초 단위로 한 줄에 출력한다.