[NEERC2016] Delight for a Cat

一只猫猫在连续的 $n$ 个小时中可以进行睡觉或进食两种动作。一个小时内只能选择其中一种进行。 现在你知道这只猫在接下来的这 $n$ 个小时中每第 $i$ 个小时睡觉或进食分别获得的快乐值 $s_i$ 和 $e_i$。 但是对于每一个连续的 $k$ 个小时，这只猫必须满足在这 $k$ 个小时内至少有 $m_e$ 个小时的进食时间和 $m_s$ 个小时的睡觉时间。也就是说在这 $n$ 个小时中的 $n-k+1$ 个 $k$ 长连续区间必须满足睡觉时间 $\geq m_s$ ，进食时间 $\geq m_e$。 现在小猫想知道自己这 $n$ 个小时最多能获得多少快乐值以及相对应的方案。 输入： 第一行分别输入 $n,k,m_s,m_e$ 。 第二行输入 $n$ 个数字 $s_1,s_2,\dots, s_n$ 分别代表每个小时如果睡觉可以获得的快乐值。 第三行输入 $n$ 个数字 $e_1,e_2,\dots,e_n$ 分别代表每个小时如果进食可以获得的快乐值。 输出： 第一行输出可以获得的最大快乐值。 第二行输出**一个合法方案**，$n$ 个字符表示每个小时进行的动作。第 $i$ 个字符用 `S` 表示第 $i$ 个小时在睡觉，或用 `E` 表示第 $i$ 个小时在进食。

A cat is going on an adventure. Each hour, the cat can be either sleeping or eating. The cat cannot be doing both actions at the same hour, and the cat is doing exactly one of these actions for the whole hour. For each of the next $n$ hours, the amount of delight the cat is getting if it is sleeping or eating during that hour is known. These amounts can be different for each hour. An integer time period $k$ is also known. Among every $k$ consecutive hours, there should be at least $m_{s}$ hours when the cat is sleeping, and at least $m_{e}$ hours when the cat is eating. So, there are exactly $n − k + 1$ segments of $k$ hours for which this condition must be satisfied. Find the maximum total amount of delight the cat can get during the next $n$ hours.

The first line of the input contains four integers $n , k , m_{s},$ and $m_{e} (1 \le k \le n \le 1000$ ; $0 \le m_{s}, m_{e} \le k$ ; $m_{s} + m_{e} \le k)$ -- the number of upcoming hours, the length of the period (in hours), and the minimum number of hours the cat should be sleeping and eating out of every $k$ consecutive hours, respectively. The second line contains $n$ integers $s_{1}, s_{2},$ . . . , $s_{n} (0 \le s_{i } \le 10^{9}$ ) -- the amount of delight the cat gets when it is sleeping during the first, the second, $ \cdots ,$ the n-th hour. The third line contains $n$ integers $e_{1}, e_{2},$ . . . , $e_{n} (0 \le e_{i} \le 10^{9}$ ) -- the amount of delight the cat gets when it is eating during the first, the second, $ \cdots ,$ the n-th hour.

In the first line, output a single integer -- the maximum total amount of delight the cat can get during the next $n$ hours. In the second line, output a string of length $n$ consisting of characters `S` and `E`. The i-th character of this string should correspond to whether the cat should sleep $(`S`)$ or eat $(`E`)$ in the i-th hour to get the maximum total amount of delight out of these $n$ hours.

10 4 1 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

69
EEESESEESS

Time limit: 2 s, Memory limit: 512 MB.