Nguồn: PREVOI
SuperCodes
là đội trưởng huyền thoại của trường XYZ đã nhiều lần vô địch cuộc thi lập
trình viên vũ trụ ACM Universe Final. Theo thể thức cuộc thi, mỗi đội tham dự
có đúng 3 thành viên và được giao duy nhất một máy tính chính vì vậy việc điều
phối công việc vô cùng quan trọng. Trong đội SuperCodes – đội trưởng là PHUONGHD
- người nắm giữ vai trò quan trọng đó.
Đề thi ACM
năm nay gồm có 2N bài được đánh số từ 1 đến 2N. Bằng kỹ thuật thiết kế thuật
toán siêu việt, chỉ vài giây sau khi đọc đề PHUONGHD đã có lời giải cho 2N bài
toán. Vấn đề còn lại là phân công 2 người lập trình bởi PHUONGHD không quen với
ngôn ngữ lập trình mới vừa được đưa vào sử dụng tại cuộc thi.
Do rất hiểu 2 thành viên Tí và Tèo trong đội, PHUONGHD
biết rằng nếu giao bài thứ i cho Tí thì mất ai giây, cũng bài đó nếu
giao cho tèo sẽ mấy bi giây để hoàn thành (1≤i≤2N). Nhiệm vụ của bạn
làm giúp PHUONGHD phân công cho 2 thành viên, mỗi người làm đúng N bài sao cho
tổng thời gian lập trình cả 2N bài là ít nhất.
Dữ liệu vào: Từ tệp văn
bản ACM.INP
+ Dòng 1 chứa
số nguyên dương N (N≤4.105)
+ 2N dòng
tiếp theo, dòng thứ i chứa 2 số nguyên dương ai, bi (ai,
bi≤100) cách nhau bởi dấu cách.
Dữ liệu ra: ghi vào tệp
văn bản ACM.OUT một số nguyên duy nhất là thời gian lập trình cả 2N bài theo
phương án phân công tìm được.
Chú ý:
40% số điểm
tương ứng với test có N≤1000
30% số điểm
tương ứng với test có 104 ≤N≤ 105
30% số điểm
tương ứng với test có 3.105≤N≤ 4.105
|
Ví dụ
|
|
|
ACM.INP
|
ACM.OUT
|
|
2
2 1
3 2
5 3
1 2
|
8
|
