Danh sách Ưu và Nhược điểm

Trong một buổi họp nhóm, FullHouse Dev đang thảo luận về một bài toán thú vị liên quan đến việc tối ưu hóa "hạnh phúc". Với sự hào hứng và tò mò, họ bắt đầu phân tích vấn đề này, hy vọng tìm ra giải pháp tối ưu.

Bài toán

FullHouse Dev được cung cấp một danh sách gồm \(n\) cô gái, và họ cần tính toán "hạnh phúc" tối đa có thể đạt được bằng cách chọn đúng 2 cô gái. Mỗi cô gái được đặc trưng bởi hai thông số:

• favour: nếu cô gái này được chọn, hạnh phúc sẽ tăng lên một lượng bằng giá trị này.
• anger: nếu cô gái này không được chọn, hạnh phúc sẽ giảm đi một lượng bằng giá trị này.

Nhiệm vụ là tìm ra "hạnh phúc" tối đa mà có thể đạt được. Lưu ý rằng kết quả có thể là số âm.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(t\), biểu thị số lượng test case.
• Với mỗi test case:
  • Dòng đầu tiên chứa số nguyên \(n\).
  • \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi khoảng trắng, biểu thị favour và anger của cô gái thứ \(i\).

OUTPUT FORMAT:

• Với mỗi test case, in ra một dòng chứa giá trị hạnh phúc tối đa có thể đạt được.

Ràng buộc:

• \(1 \leq t \leq 10\)
• \(2 \leq n \leq 10^5\)
• \(0 \leq \text{favour}[i], \text{anger}[i] \leq 10^9\)
• Không có file đầu vào nào vượt quá 4MB.

Ví dụ

INPUT

1
4
2 3
10 2
11 5
4 1

OUTPUT

17

Giải thích

Trong ví dụ này, FullHouse Dev nên chọn cô gái thứ 2 và thứ 3. Hạnh phúc tổng cộng sẽ là: 10 (favour của cô gái 2) + 11 (favour của cô gái 3) - 1 (anger của cô gái 4) - 3 (anger của cô gái 1) = 17.