Maximizing Cat Delight Under Sliding Window Constraints

A cat is about to embark on an adventure over the next n hours. In each hour, the cat can either be sleeping or eating but not both. For each hour, the delight the cat receives from sleeping and eating are given. Furthermore, there is a sliding window condition: for every consecutive k hours, there must be at least m_s hours of sleeping and at least m_e hours of eating.

Formally, let the decision for hour i be represented by a binary variable x[i] where:

$$x[i]=\begin{cases} 0 & \text{if the cat sleeps in hour } i,\\ 1 & \text{if the cat eats in hour } i. \end{cases} $$

For each hour i (from 1 to n), two integers are given: the delight for sleeping, \(S[i]\), and eating, \(E[i]\). The total delight is computed as:

$$\text{Total Delight} = \sum_{i=1}^{n} \Bigl[(1-x[i]) \cdot S[i] + x[i] \cdot E[i]\Bigr]. $$

However, the decision sequence must satisfy the following sliding window constraints: for every consecutive k hours (there are exactly n - k + 1 such segments), if we let \(T = \sum_{j=i}^{i+k-1} x[j]\) be the number of hours in which the cat eats in that segment, then the following must hold:

$$m_e \leq T \leq k - m_s.$$

Your task is to choose an action for each hour so that all window constraints are satisfied and the total delight is maximized.

inputFormat

The first line of input contains four integers: n, k, m_s, and m_e.

Then follow n lines. The i-th of these lines contains two non-negative integers: S[i] and E[i], which represent the delight received if the cat sleeps or eats in the i-th hour, respectively.

You may assume that the input values are such that a valid schedule exists.

outputFormat

Output a single integer --- the maximum total delight the cat can achieve while meeting the sliding window conditions.

sample

5 3 1 1
3 2
2 5
4 1
1 3
2 4

19