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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vodivide


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
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 ???
2016-09-20 03:54:01 minhsn
tr4u cu~ng 4c m4` c4'c pn .
2016-08-18 09:19:42
Anh Tuấn nói tào lao ấy, test đề ra 28 là đúng rồi
2016-02-22 09:35:31 xin đừng quên tôi
Tham khảo tại: http://yeulaptrinh.pw/66/spoj-vodivide/
2016-02-01 08:48:01
THAM KHAO: http://codevnspoj.blogspot.com/
2015-12-09 14:51:39 Anh Tuấn
nếu ban sơn chon 1 với 6 thì xử lí thế nào
p/s: test đề ra 43
2015-12-06 12:41:11 Ðặng Phương Tân
Heap thế nào vậy mấy bác? o.O
2015-10-26 09:36:36 Lê Hoàng Vũ
Bài này thuật toán chuẩn phải là Heap :))
2015-10-05 06:24:59 bembembem
heap cũng AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.