Total Feasibility Count

You are given a contest consisting of n problems, where the i-th problem has a difficulty value \(v_i\). You are also given a positive integer \(k\) (with \(k \le n\)), which is used to define the feasibility of a problem.

For every problem \(x\) with \(x \ge k\), define its feasibility \(a_x\) as follows: Consider the first \(x\) problems and sort their difficulty values in increasing order. Then \(a_x\) is defined as the sum of the largest \(k\) values among these \(x\) problems (i.e. the sum of the \(k\) highest difficulties).

Because the first \(k-1\) problems are too easy, their feasibility is not considered. The total feasibility of the contest is defined as \[ F = \sum_{x=k}^{n} a_x. \]

You have the power to change the difficulty of exactly m problems (\(0 \le m \le n\)) to any positive integer you want. With this ability, you wish to adjust the contest so that the total feasibility \(F\) lies in the interval \([l, r]\) (inclusive).

Your task is to determine how many distinct total feasibility values can be achieved by choosing a set of exactly m problems to modify and assigning them appropriate positive integer difficulties, such that the final total feasibility \(F\) is in \([l, r]\).

Note: When \(m = 0\) (i.e. no changes are allowed), there is only one possible total feasibility (which might or might not lie in \([l, r]\)). For \(m \ge 1\) the achievable values may be sparse—not every value in \([l, r]\) need be attainable.

inputFormat

The first line contains five integers \(n, m, k, l, r\) separated by spaces.

The second line contains \(n\) positive integers \(v_1, v_2, \dots, v_n\) separated by spaces, representing the difficulty values of the problems.

It is guaranteed that \(1 \le k \le n\) and \(0 \le m \le n\).

outputFormat

Output a single integer which is the number of distinct total feasibility values \(F\) (as defined below) that lie in the interval \([l, r]\) and can be achieved by modifying exactly \(m\) problems’ difficulties.

The feasibility \(F\) is computed as follows. For \(x \ge k\), define \[ a_x = \text{sum of the largest } k \text{ elements among } \{d_1, d_2, \dots, d_x\}, \] where \(d_i\) is the final difficulty of problem \(i\) (either unchanged or modified). Then \[ F = \sum_{x=k}^{n} a_x. \]

sample

2 1 1 50 250
100 50

150