# 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.

## Constraints

1 <= N <= 20000 1 <= arr[i] <= 10^5 1 <= K <= N/3

## Format

### Input

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

### Output

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.

## Example

Sample Input

8
1 2 1 2 6 7 5 1
2

### Sample Output

23 0 3 5