Maximizing X's Mood

X loves quiet environments because they improve his mood. Over a period of (N) minutes, X experiences a mood effect each minute that depends on whether he is indoors or outdoors. Specifically, for each minute (i) ((1 \leq i \leq N)), two integers are given: (A_i) when he is indoors and (B_i) when he is outdoors. Initially (at the beginning of minute 1) he may choose either state for free. However, starting from the beginning of minute 2, he may decide to switch his location (i.e. from indoors to outdoors or vice versa) at the beginning of a minute. He is allowed to switch at most (K) times during these (N) minutes (note that a switch at the beginning of minute (N) is allowed, while no switch is allowed at the beginning of minute 1).\n\nMoreover, to discourage overly frequent switching, if two consecutive switches occur within an interval of (\leq T) minutes, an extra penalty of (P) (in mood points) is imposed at the moment of the later switch. Formally, if a switch is executed at the beginning of minute (t_a) and the previous switch (if any) was executed at the beginning of minute (t_b), and if (t_a - t_b \leq T), then an extra penalty of (P) is subtracted from his mood. (The first switch does not incur any penalty since there is no previous switch.)\n\nDuring each minute, after the (possible) switch decision at its beginning, X’s mood is increased by the corresponding effect of his current state for that minute. The mood updates add cumulatively. Your task is to determine the maximum final mood value at the end of minute (N) that X can achieve by planning his switching optimally.\n\nAll formulae are in (\LaTeX) format.

inputFormat

The first line contains four integers \(N\), \(K\), \(T\), and \(P\) \(\,(1 \le N, K \le 100,\, T \geq 0,\, P \geq 0)\). Here, \(P\) is the penalty incurred (i.e. subtracted from mood) if the time interval between two switches is \(\le T\) minutes. The following \(N\) lines each contain two integers \(A_i\) and \(B_i\) representing the mood effect values if X is indoors and outdoors, respectively, in the \(i\)-th minute.

Note: A switch (i.e. changing state) is allowed at the beginning of any minute except the first minute. Also the initial choice of state at minute 1 does not count as a switch.

outputFormat

Output a single integer, the maximum mood value X can achieve at the end of minute \(N\).

sample

3 1 1 5
1 2
3 1
-1 4

8