Bảo lái xe qua con đường dài \(100\) dặm và sau đó Bảo đã bị bắt do chạy quá tốc độ nhưng anh ấy đã không chấp nhận cáo buộc này và muốn tự xác định điều đó. Con đường được chia thành \(N\) đoạn, mỗi đoạn có chiều dài tính bằng dặm và giới hạn tốc độ từ \(1\) đến \(100\) dặm/giờ. Chiều dài của tất cả các đoạn \(N\) cộng lại là \(100\) dặm. Ví dụ, đoạn đầu có thể dài \(45\) dặm với giới hạn tốc độ \(70\), sau đó kết thúc bằng đoạn \(55\) dặm với giới hạn \(60\).

Chuyến đi của Bảo cũng được mô tả bằng \(M\) đoạn. Trong mỗi đoạn, anh ấy di chuyển một số dặm nhất định với tốc độ nhất định. Ví dụ, anh ấy có thể bắt đầu bằng cách đi \(50\) dặm với tốc độ \(65\), sau đó \(50\) dặm với tốc độ \(55\). Chiều dài của tất cả các đoạn \(M\) cộng lại là \(100\) dặm. Xe của Bảo có thể đi nhanh nhất \( 100 \) dặm/giờ.

Dựa trên đề bài trên, hãy xác định số dặm/giờ cao nhất mà Bảo lái xe vượt quá giới hạn tốc độ trong bất kỳ phần nào của chuyến đi.

INPUT FORMAT

Dòng đầu tiên chứa \(N\) và \(M\), phân tách bằng dấu cách. \(N\) dòng tiếp theo mô tả mỗi đoạn đường, bao gồm chiều dài và giới hạn tốc độ. \(M\) dòng tiếp theo mô tả mỗi đoạn trong chuyến đi của Bảo, bao gồm chiều dài và tốc độ mà xe chạy.

OUTPUT FORMAT

Hãy xuất một dòng chứa số dặm/giờ vượt quá giới hạn tốc độ cao nhất mà Bảo lái trong bất kỳ phần nào của chuyến đi. Nếu anh ấy không bao giờ vượt quá giới hạn tốc độ, hãy xuất \(0\).

Ví dụ:

Input

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

Output

5

Trong ví dụ này, con đường có ba đoạn (40 dặm với tốc độ giới hạn 75 dặm/giờ, tiếp theo là 50 dặm với giới hạn 35 dặm/giờ, sau đó là 10 dặm với giới hạn 45 dặm/giờ). Bảo lái qua ba đoạn (40 dặm với tốc độ 76 dặm/giờ, 20 dặm với tốc độ 30 dặm/giờ và 40 dặm với tốc độ 40 dặm/giờ). Trong đoạn đầu tiên của mình, anh ấy hơi quá tốc độ, nhưng đoạn cuối cùng là vi phạm nghiêm trọng nhất, phần nào anh ấy chạy quá 5 dặm/giờ so với giới hạn tốc độ. Do đó, câu trả lời đúng là 5.

Giải thích ví dụ mẫu:

• Ví dụ 1:

  • Con đường có ba đoạn: 40 dặm với tốc độ giới hạn 75 dặm/giờ, 50 dặm với giới hạn 35 dặm/giờ, và 10 dặm với giới hạn 45 dặm/giờ.
  • Bảo lái xe qua ba đoạn: 40 dặm với tốc độ 76 dặm/giờ, 20 dặm với tốc độ 30 dặm/giờ, và 40 dặm với tốc độ 40 dặm/giờ.
  • Đoạn đầu tiên của Bảo lái xe có phần vượt quá tốc độ giới hạn là 76 - 75 = 1 dặm/giờ.
  • Đoạn thứ hai của Bảo lái xe có phần vượt quá tốc độ giới hạn là 30 - 35 = -5 dặm/giờ (không vượt).
  • Đoạn thứ ba của Bảo lái xe có phần vượt quá tốc độ giới hạn là 40 - 45 = -5 dặm/giờ (không vượt).
  • Vượt quá tốc độ cao nhất là 1 dặm/giờ.

  Trong ví dụ này, Bảo vượt quá tốc độ giới hạn cao nhất là 5 dặm/giờ trong đoạn đầu tiên, vì vậy kết quả là 5 dặm/giờ.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House