Video Café in Uzhlandia
The 2014 World Ice Hockey Championship is set to take place in Uzlandia. To ensure a successful event, the host nation must adhere to several requirements from the International Ice Hockey Federation. The matches are scheduled in the cities of Uzhkachevo and Uzhkovel, both connected by a direct highway. In Uzlandia, all city names start with "Uzh."
The Federation has observed that none of the N campsites along the Uzhkachevo - Uzhkovel highway currently have a video café. A video café is similar to a regular roadside café but is equipped to broadcast sports events. The Federation has mandated that video cafés be established at K out of the N campsites. They have set the following criteria for the placement of each video café:
1. The distance between any video café and the previous one on the highway (if any) must be at least A km and no more than B km.
2. The distance between any video café and the next one on the highway (if any) must be at least A km and no more than B km.
3. The distance from Uzhkachevo and Uzhkovel to the nearest video café should be no less than A km and no more than B km.
Example Figure: N=5, K=3, A=20, B=70.
For each i-th video café, define the coefficient Z_i as the distance from this video café to all others. The Federation has determined that a higher sum of the coefficients Z_i allows travelers to receive match information more promptly.
Your task is to calculate the maximum sum of Z_i that can be achieved by constructing K video cafés that satisfy all the Federation's requirements. Each campsite can host only one video café, and a video café can only be located at a campsite.
**Input Format:** The first line contains two integers, N, K (1 ≤ K ≤ N ≤ 1000). The second line contains two integers, A, B (1 ≤ A < B ≤ 10^9). The third line contains one integer, S (1 ≤ S ≤ 10^9), representing the distance between Uzhkachevo and Uzhkovel. The fourth line contains N integers, C_i (0 < C_i < S, C_i < C_j if i < j), indicating the distance of the i-th campsite from Uzhkachevo.
**Output Format:** Output a single integer, the maximum sum of the coefficients Z_i for constructing K video cafés. A solution is guaranteed to exist.
**Explanation for Examples:**
In the first example, the selected campsites are {1, 2, 4}.
In the second example, the selected campsites are {2, 5, 8, 10}.