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

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

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

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

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

对于 20% 20\% 20% 的数据，n≤20 n \leq 20 n≤20；
对于 40% 40\% 40% 的数据，n≤100 n \leq 100 n≤100；
另外有 20% 20\% 20% 的数据，ms=0 \text{ms} = 0 ms=0；
对于 100% 100\% 100% 的数据，1≤k≤n≤1000;0≤ms,me,ms+me≤k;0≤ei,si≤109 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 1≤k≤n≤1000;0≤ms,me,ms+me≤k;0≤ei,si≤109；
对于每个测试点，假如你回答对了第一行，那么你能获得 40% 40\% 40% 的分数，假如你两行都正确，那么你能获得 100% 100\% 100% 的分数。