Captain Reyes runs a supply convoy along a single desert highway. The crates waiting at base camp are lined up in a fixed order on the loading dock, and their order can never be changed — trucks must scoop up a contiguous run of crates exactly as they sit on the dock.

Every truck also drags a fixed escort trailer, whose weight is added once to whatever load the truck is already carrying. One of the safety rules caps how many crates a single truck bed may physically hold, regardless of how light those crates are.

Reyes has a fixed number of trucks available and must use every single one of them, dividing the full line of crates into exactly k non-empty contiguous groups, with no group containing more than the allowed number of crates.

Reyes wants to know the smallest possible value for the heaviest truck's total load (crates + escort trailer), if the crates are split as evenly as possible into those many contiguous, capacity-respecting groups.

Function Description

Implement the function:

minMaxConvoyLoad

Parameters

• n — the number of crates on the dock.
• k — the number of trucks that must be used. The dock is split into exactly k contiguous non-empty groups.
• escort — the fixed escort trailer weight added once to every truck's load.
• maxCrates — the maximum number of crates that a single truck can carry.
• weights[] — an array containing the weight of each crate in their fixed order.

Requirements

• The order of crates cannot be changed.
• Every truck must receive at least one crate.
• Each truck must receive a contiguous segment of the array.
• No truck can carry more than maxCrates crates.
• Exactly k trucks must be used.
• The load of a truck is the sum of its assigned crate weights plus escort.
• Return the minimum possible value of the maximum truck load.

Example

Input

6
3
2
2
10 1 1 1 1 10

Output

13

Explanation

The crates can be divided into 3 contiguous groups:

[10]
[1 1]
[1 1 10]

Their crate loads are:

10, 2, 12

Adding the escort weight 2 to every truck:

12, 4, 14

So the maximum load is 14.

The objective is to find the minimum possible maximum load among all valid contiguous partitions.