Bài tập chưa có test

Pi và Po tham gia một trò chơi trên truyền hình. Trong trò chơi, có \(n\) đồ vật được xuất hiện trên màn hình máy tính, đồ vật thứ \(i\) có giá trị \(a_{i}\). Luật chơi như sau:

+ Hai người luân phiên nhau thực hiện lượt chơi của mình.

+ Pi là người chơi trước.

+ Mỗi người chơi thực hiện đúng \(k\) lượt chơi.

+ Trong mỗi lượt chơi, người chơi sẽ chọn một đồ vật có giá trị lớn nhất đang xuất hiện trên màn hình. Có một ngoại lệ là Po được phép chọn 2 đồ vật có giá trị lớn nhất ở lượt chơi thứ \(k\). Sau khi được chọn, đồ vật đó sẽ bị xóa khỏi màn hình.

Yêu cầu: Hãy cho biết tổng giá trị các đồ vật của mỗi người là bao nhiêu sau khi thực hiện \(k\) lượt chơi?

Dữ liệu vào: Từ tệp văn bản CHONDO.INP có cấu trúc:

+ Dòng đầu tiên ghi hai số nguyên dương \(n,\ k\ \left( 1 \leq 2 \times k + 1 \leq n \leq 10^{5} \right)\);

+ Dòng thứ hai ghi lần lượt các số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{9};i = 1\ldots n)\).

Kết quả: Ghi vào tệp văn bản CHONDO.OUT trên hai dòng

+ Dòng đầu tiên ghi tổng giá trị các đồ vật Pi đã chọn;

+ Dòng thứ hai ghi tổng giá trị các đồ vật Po đã chọn.

Ví dụ:

CHONDO.INP	CHONDO.OUT
7 2 6 5 2 7 1 4 3	12 13

Giải thích ví dụ:

+ Pi chọn các đồ vật có giá trị 7 và 5; tổng nhận được là 12;

+ Po chọn các đồ vật có giá trị 6 và 4 và 3; tổng nhận được là 13.

Ràng buộc:

+ Có 50% số test tương ứng với 50% số điểm có \(n \leq 1000\);

+ Có 50% số test còn lại tương ứng với 50% số điểm có \(n \leq 10^{5}\).