Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VODIVIDE - VOI 2015 Day 2 - 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ự từ 1->N. Đồng tiền thứ i Vinh định giá nó là ai còn Sơn định giá nó là bi. 

Vinh và Sơn tiền hành phân chia số tiền này, lần lượt thực hiện 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ố ai, bi (i=1..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 a1, a2, ..., aN mỗi số ko vượt quá 400000

Dòng thứ 3 chứa N số nguyên dương b1, b2, ..., bN 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.

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

Example

Input:
6
6 10  11 18 5 14
1 7 6 12 15 1
Output: 
28
5 1
2 6
3 4

Giới hạn:
30% số test với N<=5000 và ai = bi với i = 1..N;
30% số test với N<=20
40% số test còn lại với N<=5000 

Được gửi lên bởi:VOJ Team
Ngày:2015-01-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VOI15 day 2

hide comments
2017-12-26 17:56:21
test yếu vậy làm 2 sub đầu mà được 90.91 ?
2017-11-11 03:10:36
code ac này các bác
http://bfy.tw/EySq
2017-09-18 11:42:00


THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/66/spoj-vodivide/



2017-08-14 15:31:25
Code O(nlogn):
https://vietcodes.github.io/code/42/
2016-11-11 19:28:06
gg ez http://liink.pw/WrOZVm
2016-11-11 17:50:36
ax mình nhầm phải là 4phía. pn có thể tham khảo code mình ở đây https://goo.gl/vQujkw
2016-11-11 17:48:11
đưa về 3 phía kiểu gì pạn, mình đưa về 4 phía được thôi :|
2016-11-11 17:46:26
cặp ghép cực đại với giá trị cực tiểu trên đồ thị 3 phía thôi mà
2016-11-11 17:44:18
trâu N ^ 3 log AC @@
2016-10-18 15:00:40
nếu 2 đông = nhau thì thằng vinh nó lấy đồng nào ???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.