VOI 15 Bài 5 - Chia phần

Xem dạng PDF

Gửi bài giải


Điểm: 0,58 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VOI15 day 2
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Vinh và Sơn có ~N~ đồng tiền cổ, ~N~ là số chẵn. Ta tạm đánh số các đồng tiền cổ này theo thứ tự ~1, 2, \dots, N~. Đồng tiền thứ ~i~ Vinh định giá nó là ~a_{i}~ còn Sơn định giá nó là ~b_{i}~.

Vinh và Sơn tiền hành phân chia số tiền này, lần lượt thực hiện ~\frac{N}{2}~ lượt. Ở lượt chơi thứ ~t~, Sơn lấy ra 2 đồng tiền, Vinh sẽ lấy đồng tiền nào có giá trị lớn hơn trong 2 đồng tiền theo như Vinh định giá, và Sơn sẽ lấy đồng tiền còn lại.

Sơn biết tất cả các số ~a_{i}, b_{i}~ ~(i = 1, 2, \dots, N)~ và mỗi bước Sơn được quyền chọn cách lấy 2 đồng tiền tùy theo ý thích của mình.

Hãy giúp Sơn tiền hành việc phân chia các đồng tiền sao cho tổng giá trị các đồng tiền Sơn nhận được là lớn nhất có thể.

Input

  • Dòng đầu tiên chứa số nguyên dương chẵn ~N~ là số đồng tiền.
  • Dòng thứ 2 chứa ~N~ số nguyên dương ~a_{1}, a_{2}, \dots, a_{N}~ mỗi số ko vượt quá ~400000~.
  • Dòng thứ 3 chứa ~N~ số nguyên dương ~b_{1}, b_{2}, \dots, b_{N}~ mỗi số ko vượt quá ~400000~.

Output

Dòng đầu tiên ghi ra tổng số tiền lớn nhất mà Sơn nhận được.

~\frac{N}{2}~ dòng tiếp theo mỗi dòng ghi cặp 2 chỉ số các đồng tiền mà Sơn lấy ra theo đúng thứ tự mỗi lượt thực hiện chia phần. Nếu có nhiều phương án in ra 1 phương án bất kì.

Giới hạn

  • ~30\%~ số test với ~N \leq 5000~ và ~a_{i}~ = ~b_{i}~ với ~i = 1~, ~2~, ..., ~N~;
  • ~30\%~ số test với ~N \leq 20~.
  • ~40\%~ số test còn lại với ~N \leq 5000~.

Sample Input

6
6 10 11 18 5 14
1 7 6 12 15 1

Sample Output

28
5 1
3 6
2 4

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.