NOTMED - Tìm các số lớn nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: ami

.

          Sau khi tích cóp được kha khá tiền từ nghề dạy học, Ami quyết định mua phi thuyền để du hành vũ trụ. Mặc dù ít khi tiêu xài, nhưng khi đã tiêu tiền thì Ami phải mua hàng hiệu. Và về buôn bán tàu vũ trụ thì công ty DDT là thương hiệu số 1. Hiện tại, cửa hàng DDT đang bày bán n loại phi thuyền. Mỗi loại phi thuyền có giá tiền là ai. Chiến thuật marketing của cửa hàng DDT cũng rất đặc biệt. Mỗi giây, họ lại giới thiệu một phi thuyền khác để khách hàng dễ lựa chọn. Nghĩa là nếu có n phi thuyền thì ở giây đầu khách hàng chỉ biết giá, mẫu mã của 1 phi thuyền, ở giây thứ 2 thì biết 2 phi thuyền (bao gồm cả phi thuyền 1),…

          Ami cần mua k phi thuyền và k phi thuyền đó phải là đắt nhất, vì Ami giàu mà. Do đó bắt đầu từ giây thứ k , Ami cần các bạn tính xem, tổng giá tiền của k phi thuyền đắt nhất là bao nhiêu.

Dữ liệu vào

Dòng đầu là 2 số nguyên dương n và k (n , k <= 105).

Dòng tiếp theo là n số nguyên a1,a2,..,an (|a­i| <= 109) là các giá tiền của phi thuyền sẽ xuất hiện ở giây thứ i.

Dữ liệu ra

Gồm n – k + 1 dòng, dòng thứ i là tổng giá của k phi thuyền đắt nhất ở giây thứ k + i – 1.

Ví dụ

Input

5 3

5 4 3 2 8

Output

12

12

17

Giải thích

Ở giây thứ 3, các phi thuyền xuất hiện là |5 4 3|. Do đó kết quả là 5 + 4 + 3 = 12.

Ở giây thứ 4, các phi thuyền xuất hiện là |5 4 3 2|. Do đó kết quả là 5 + 4 + 3 = 12.

Ở giây thứ 5, các phi thuyền xuất hiên là |5 4 3 2 8|. Do đó kết quả là 5 + 4 + 8 = 17.

Back to Top