HUT-Organization là một tập đoàn đa lĩnh vực, trong đó FIT là một công ty thành viên của HUT-Organization chuyên nhập khẩu thiết bị từ các M quốc gia sản xuất và xuất khẩu sang N quốc gia tiêu dùng.

Tuy nhiên, do các chính sách về thuế quan hiện nay và thời gian thương mại giữa các quốc gia, FIT chỉ có thể ký hợp đồng với một quốc gia sản xuất và một quốc gia tiêu dùng duy nhất. Sau khi ký hợp đồng, FIT có thể:

• Mua 1 đơn vị hàng hóa mỗi ngày từ quốc gia sản xuất thứ i với giá P_i, bắt đầu từ ngày quốc gia đó cho phép xuất khẩu là ngày D_i.
• Bán 1 đơn vị hàng hóa mỗi ngày cho quốc gia tiêu dùng j với giá Qj, kết thúc vào trước ngay ngày hạn chót quốc gia đó có thể nhận hàng Eⱼ
• Một ngày, FIT chỉ có thể thực hiện 1 giao dịch mua – bán, nếu cả hai phía đều chấp nhận giao dịch tại ngày đó và giao dịch hợp lệ khi Dᵢ < Eⱼ. Tức là FIT có ít nhất một ngày để mua – bán hàng hóa

Nhiệm vụ: Bạn hãy chọn một cặp quốc gia sản xuất – quốc gia tiêu dùng sao cho tổng lợi nhuận FIT thu được là lớn nhất.

• Dòng đầu chứa hai số nguyên M và N — số quốc gia sản xuất và số quốc gia tiêu dùng (1 ≤ M, N ≤ 5×10⁵)
• M dòng tiếp theo: mỗi dòng chứa hai số nguyên Pᵢ và Dᵢ — giá xuất khẩu và ngày bắt đầu xuất khẩu của quốc gia sản xuất thứ i
• N dòng tiếp theo: mỗi dòng chứa hai số nguyên Q_j, Eⱼ — giá nhập khẩu, và ngày ngay sau ngày cuối cùng mà quốc gia đó có thể nhận hàng

Một số nguyên duy nhất là lợi nhuận lớn nhất có thể thu được. Nếu không thể thực hiện bất kỳ giao dịch nào, xuất ra giá trị 0.

• (1) Chọn quốc gia sản xuất 2 (giá xuất 2, từ ngày 1) và quốc gia tiêu dùng 2 (giá nhập 7, nhận đến ngày 2).
  Giao thương được 1 ngày → mỗi ngày lời 7 - 2 = 5. Tổng lợi nhuận 1 * 5 = 5 là lớn nhất

  • Còn nếu chọn quốc gia sản xuất 2, quốc gia tiêu dùng 1 thì được 4 * 1 = 4
  • Còn nếu chọn quốc gia sản xuất 1, quốc gia tiêu dùng 1 thì được lợi nhuận 2 * 2 = 4

• (2) Chọn Quốc gia sản xuất 1 (giá 10, từ ngày 10)

  • Quốc gia tiêu dùng 1(giá nhập 9, đến ngày 11) → lỗ vì 9-10 = -1.
  • Quốc gia tiêu dùng 2 (giá nhập 11, đến ngày 9) → không giao nhau → Không có cặp hợp lệ → Output: 0