题目描述

你养了一只猫，为了让它快乐地成长，你需要合理地安排它每天的作息时间。假设一天分为 $ n $ 个时刻，猫在每个时刻要么是吃东西，要么是睡觉。在第 $ i $ 个时刻，假如猫是去吃东西，那么它能获得愉悦值 $ e_i $，假如是去睡觉，那么能获得的愉悦值为 $ s_i $。

猫要成长，不仅仅需要快乐，还需要健康的作息。经过研究，对于每一个连续的长度为 $ k $ 的作息区间，即所有的时刻区间 $ [i, i + k - 1], 1 \leq i \leq n − k + 1 $，猫都要至少有 $ \text{ms} $ 的时刻用来睡觉，$ \text{me} $ 的时刻用来吃东西，这样猫才能健康成长。

现在你想合理地安排一天中的这 $ n $ 个时刻，使得猫在能健康成长的前提下，获得尽量多的愉悦值。

输入格式

第一行四个整数 $ n, k, \text{ms}, \text{me} $。
第二行包含 $ n $ 个整数，代表 $ s_i $。
第三行包含 $ n $ 个整数，代表 $ e_i $。

输出格式

第一行一个整数，代表猫能获得的愉悦值。
第二行 $ n $ 个字符，可以为 $ \texttt{S} $ 或 $ \texttt{E} $，代表猫在某个时刻是在睡觉（$ \texttt{S} $）还是在吃东西（$ \texttt{E} $）。

样例

input

5 4 2 2
4 8 6 2 2
4 6 9 6 0

output

29
SSEES

数据范围与提示

对于 $ 20\% $ 的数据，$ n \leq 20 $；
对于 $ 40\% $ 的数据，$ n \leq 100 $；
另外有 $ 20\% $ 的数据，$ \text{ms} = 0 $；
对于 $ 100\% $ 的数据，$ 1 \leq k \leq n \leq 1000; 0 \leq \text{ms}, \text{me}, \text{ms} + \text{me} \leq k; 0 \leq e_i, s_i \leq 10 ^ 9 $；
对于每个测试点，假如你回答对了第一行，那么你能获得 $ 40\% $ 的分数，假如你两行都正确，那么你能获得 $ 100\% $ 的分数。