Chia phần

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ể.

Dữ liệu vào

• 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ố không 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ố không vượt quá $400000$.

Dữ liệu ra

• 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ì.

Ràng buộc

• $2\le N\le 5000$, $N$ chẵn.
• $1\le a_i,b_i\le 400000$.
• Các giá trị $a_1,a_2,\dots ,a_N$ đôi một khác nhau (nên trong mỗi lượt, đồng tiền Vinh lấy được xác định duy nhất).

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 5000$ và $a_i=b_i$ với $i=1,2,\dots ,N$.
• Subtask 2 ($30\%$ số điểm): $N\le 20$.
• Subtask 3 ($40\%$ số điểm): $N\le 5000$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ