Thermal Partition

The rocket was screaming through the upper atmosphere now, plasma trailing behind it like a comet's tail. The heat shield tiles glowed orange through the observation cameras, and the temperature readouts climbed with every second. Adel gripped the armrest as the ship shuddered—the thermal management system was failing.

The tiles were arranged in a line along the hull, each one absorbing heat from the plasma. Each cooling unit managed a contiguous block of tiles, and the thermal stress on a unit was driven by the total heat load in its zone. The higher the concentration of heat in one zone, the worse the stress—and the relationship was nonlinear.

Input Format

Two lines:

• Line 1: N1 K1 N2 K2 — tile counts and zone counts for each part.
• Line 2: Space-separated non-negative integers — the heat load of each tile.

The primary cooling system has K1 cooling units. Divide the first N1 tiles into K1 contiguous zones to minimize the total thermal stress across all zones.

The stress of a zone with a total tile sum of S is the square of that sum:

stress(zone) = S * S

The total thermal stress is the sum of the stress across all K1 zones. Each zone must contain at least one tile. The zones must cover all N1 tiles in the original sequence with no gaps or overlaps.

Output: The minimum possible total thermal stress.

Example Input

5 2 10 4
4 2 3 1 5 6 2 3 7 1

Example Walkthrough

Tiles [4, 2, 3, 1, 5] with 2 cooling units:

Answer: 117.

What is the minimum total thermal stress with the primary cooling system?