P6967 [NEERC 2016] Delight for a Cat

一只猫正在进行一次冒险。 每小时，猫可以选择睡觉或吃东西。猫不能在同一小时内同时进行这两种活动，并且猫在整小时内只能进行其中一种活动。 对于接下来的 $n$ 小时，已知猫在每小时内睡觉或吃东西所获得的快乐值。这些值在每小时内可能不同。 还知道一个整数时间段 $k$。在每 $k$ 个连续的小时中，至少有 $m_{s}$ 小时猫在睡觉，至少有 $m_{e}$ 小时猫在吃东西。因此，有正好 $n - k + 1$ 个 $k$ 小时的时间段需要满足这个条件。 求猫在接下来的 $n$ 小时内所能获得的最大总快乐值。

输入的第一行包含四个整数 $n, k, m_{s},$ 和 $m_{e}$ $(1 \le k \le n \le 1000$；$0 \le m_{s}, m_{e} \le k$；$m_{s} + m_{e} \le k)$ ——即将到来的小时数、时间段的长度（以小时为单位），以及在每 $k$ 个连续小时中猫至少应该睡觉和吃东西的小时数。 第二行包含 $n$ 个整数 $s_{1}, s_{2}, \ldots, s_{n}$ $(0 \le s_{i} \le 10^{9})$ ——猫在第 1 小时、第 2 小时、$\cdots$、第 $n$ 小时睡觉时获得的快乐值。 第三行包含 $n$ 个整数 $e_{1}, e_{2}, \ldots, e_{n}$ $(0 \le e_{i} \le 10^{9})$ ——猫在第 1 小时、第 2 小时、$\cdots$、第 $n$ 小时吃东西时获得的快乐值。

在第一行输出一个整数——猫在接下来的 $n$ 小时内所能获得的最大总快乐值。 在第二行输出一个长度为 $n$ 的字符串，由字符 `S` 和 `E` 组成。这个字符串的第 $i$ 个字符应对应于猫在第 $i$ 小时应该睡觉 $(`S`)$ 还是吃东西 $(`E`)$，以便在这 $n$ 小时内获得最大的总快乐值。

时间限制：2 秒，内存限制：512 MB。 题面翻译由 ChatGPT-4o 提供。