#include<bits/stdc++.h>
using namespace std;
 
long helper(vector<int>&nums, int k) {
	multiset<long> st;
 
	long sum=0l, res=LONG_MIN;
	for(int j=0; j<nums.size(); j++) {
		sum+=nums[j];
		st.insert(nums[j]);
		if(j<k-1) continue;
		while(st.size()>k) {
			sum-=*st.begin();
			st.erase(st.begin());
		}
		res=max(res, sum);
	}
 
	return res;
}
 
long solution(vector<int>&nums, int k){
	long res1=helper(nums, k);
 
	reverse(begin(nums), end(nums));
	long res2=helper(nums, k);
 
	return max(res1, res2);
}
 
int main() {
	vector<int> nums={-5,4,-10,-1,-5,8,-3};
	cout<<solution(nums, 3)<<endl;
 
	nums={4,4,4,4,4};
	cout<<solution(nums, 4)<<endl;
 
	return 0;
}
 
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgaGVscGVyKHZlY3RvcjxpbnQ+Jm51bXMsIGludCBrKSB7CgltdWx0aXNldDxsb25nPiBzdDsKIAoJbG9uZyBzdW09MGwsIHJlcz1MT05HX01JTjsKCWZvcihpbnQgaj0wOyBqPG51bXMuc2l6ZSgpOyBqKyspIHsKCQlzdW0rPW51bXNbal07CgkJc3QuaW5zZXJ0KG51bXNbal0pOwoJCWlmKGo8ay0xKSBjb250aW51ZTsKCQl3aGlsZShzdC5zaXplKCk+aykgewoJCQlzdW0tPSpzdC5iZWdpbigpOwoJCQlzdC5lcmFzZShzdC5iZWdpbigpKTsKCQl9CgkJcmVzPW1heChyZXMsIHN1bSk7Cgl9CgkKCXJldHVybiByZXM7Cn0KCmxvbmcgc29sdXRpb24odmVjdG9yPGludD4mbnVtcywgaW50IGspewoJbG9uZyByZXMxPWhlbHBlcihudW1zLCBrKTsKCQoJcmV2ZXJzZShiZWdpbihudW1zKSwgZW5kKG51bXMpKTsKCWxvbmcgcmVzMj1oZWxwZXIobnVtcywgayk7CgoJcmV0dXJuIG1heChyZXMxLCByZXMyKTsKfQogCmludCBtYWluKCkgewoJdmVjdG9yPGludD4gbnVtcz17LTUsNCwtMTAsLTEsLTUsOCwtM307Cgljb3V0PDxzb2x1dGlvbihudW1zLCAzKTw8ZW5kbDsKIAoJbnVtcz17NCw0LDQsNCw0fTsKCWNvdXQ8PHNvbHV0aW9uKG51bXMsIDQpPDxlbmRsOwogCglyZXR1cm4gMDsKfQogCg==