시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 4 4 80.000%

문제

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 ms hours when the cat is sleeping, and at least me 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, ms, and me (1 ≤ k ≤ n ≤ 1000; 0 ≤ ms, me ≤ k; ms + me ≤ 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 s1, s2, . . . , sn (0 ≤ si ≤ 109 ) — the amount of delight the cat gets when it is sleeping during the first, the second, ..., the n-th hour.

The third line contains n integers e1, e2, . . . , en (0 ≤ ei ≤ 109 ) — the amount of delight the cat gets when it is eating during the first, the second, ..., 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

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

힌트