#6079. 「2017 山东一轮集训 Day7」养猫

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

你养了一只猫,为了让它快乐地成长,你需要合理地安排它每天的作息时间。假设一天分为 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} )。

样例

样例输入

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

样例输出

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\% 的分数。