DSA Level 2 Conceptual building blocks Dynamic Programming Maximum Sum Of Three Non-overlapping Subarrays

Maximum Sum Of Three Non-overlapping Subarrays

hard

1. You are given an array(arr) of positive numbers and a number K.
2. You have to find the maximum sum of elements in three non-overlapping subarrays.
3. Also, you have to print indices representing the starting position of every subarray.
4. If there are multiple answers, print the lexicographically smallest one.

Input Format

A number N arr1 arr2.. N numbers A number K

Output Format

4 space-separated numbers, where first number represents the maximum sum of three non-overlapping subarrays and rest three represents the starting position of every subarray.

Constraints

1 &lt;= N &lt;= 20000
1 &lt;= arr[i] &lt;= 10^5
1 &lt;= K &lt;= N/3

Example

Input

8
1 2 1 2 6 7 5 1 
2

Output

23 0 3 5

Maximum Sum Subarray With At Least K Elements

Maximum Sum Of M Non-overlapping Subarrays

Maximum Sum Of Three Non-overlapping Subarrays

Input Format

Output Format

Constraints

Example

Related Questions