Video Café in Uzhlandia#7243

Video Café in Uzhlandia

1.5 seconds

128 megabytes

Hard

As is well known, the 2014 Ice Hockey World Championship will be held in Uzhlandia. For the tournament to run successfully, the host country must meet a number of requirements set by the International Ice Hockey Federation. The hockey matches are planned to be held in the cities of Uzhkachevo and Uzhkovel, which are connected by a direct highway.

It has been noted that none of the $N$ tourist camps located along the Uzhkachevo–Uzhkovel highway currently have a video café. A video café is almost like a regular roadside café, but equipped to broadcast sports events. The Federation has decreed that video cafés should be set up in $K$ out of the $N$ camps, according to the following rules:

1. The distance between any video café and the previous one (if there is one) along the highway must be at least $A$ km and at most $B$ km. 2. The distance between any video café and the next one (if there is one) must also be at least $A$ km and at most $B$ km.

3. The distance from each city to the nearest video café must also be between $A$ and $B$ km (inclusive).

In the figure: $N = 5$ N = 5, $K = 3$ K = 3, $A = 20$ A = 20, $B = 70$ B = 70.

For each $i$ -th video café, define coefficient $Z_{i}$ Z_i as the sum of the distances from it to all other video cafés. The greater the total sum of the coefficients $Z_{i}$ Z_i, the more promptly tourists will receive information about the matches.

Your task is to determine the largest possible total sum of the coefficients $Z_{i}$ Z_i for placing $K$ video cafés according to the requirements. Only one video café can be built in each camp, and cafés can only be established in the camps.

Input

The first line contains two integers — $N, K$ $(1 \leq K \leq N \leq 1000)$ (1 \le K \le N \le 1000).

The second line contains two integers $A, B$ $(1 \leq A < B \leq 1 0^{9})$ (1 \le A < B \le 10^{9}).

The third line contains a single integer $S$ $(1 \leq S \leq 1 0^{9})$ (1 \le S \le 10^{9}) — the distance between Uzhkachevo and Uzhkovel.

The fourth line contains $N$ integers $C_{i}$ C_i $(0 < C_{i} < S, C_{i} < C_{j} if i < j)$ (0 < C_i < S, C_i < C_j \ \text{if}\ i < j) — the distances from Uzhkachevo to the $i$ -th camp.

Output

Print a single number — the maximum possible sum of the coefficients $Z_{i}$ Z_i for $K$ video cafés. A solution always exists.

Examples

Example


5 3
20 70
90
20 40 70 80 85

Example


10 4
10 35
100
8 12 22 25 37 45 62 75 86 90

Example 1

Note

In the first example, the camps ${1, 2, 4}$ \{1, 2, 4\} are chosen.

In the second — ${2, 5, 8, 10}$ \{2, 5, 8, 10\}.