题目描述

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.

样例 #1

样例输入 #1

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

样例输出 #1

69
EEESESEESS

提示

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