You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

由于碳钾钨在国际大学生魔法设计大赛中频繁打铁，他失去了参加魔女考试的资格，从此碳钾钨的魔女梦碎了QAQ。

但是碳钾钨并没有灰心，他在频繁的失败中发现了自己的打铁天赋，于是碳钾钨打算成为一个魔导铁匠。在制作金属魔导具的时候，碳钾钨又遇到了一个问题，于是他又来向你求助。

碳钾钨的魔导具上有一个长为n的符文串（为方便你处理，碳钾钨把他翻译为了一个长度为n的大写字母字符串s）和一个长度为m的制式法术单元（制式法术单元可以表示为一个长度为m的字符串t），每个符文串上的符文有自己的魔力值（用长度为n的非负整数数组a表示），制式法术单元的每个位置有一个倍率（可以由长度为m的非负整数数组b表示）。因为这串符文杂乱无章没有规律，所以这件魔导具还无法使用，你需要把魔导具上的若干个符文删去，满足剩下的符文串可以由若干个制式法术单元组成，要求你不能连续删去超过K个符文（注意是连续K个，如果K=2，那么AAAAA是不行的，但是AAAAA是可以的）。碳钾钨告诉你，一件魔导具的魔力值为每个符文的魔力值与其所对应制式法术单元的位置的倍率的乘积之和。

为方便理解，碳钾钨提供了一个例子：

现有一个魔导具，上面的符文串为CCWCKWC，分别的魔力值为1 10 5 1 100 2 100，又有一个制式法术单元，对应符文为CW，倍率分别为1 2。现在要求你不能连续删去超过K=5个符文，于是你可以把第一个C、最后一个C、和唯一的一个K删去，得到最终符文串CWCW。这样，该魔导具的魔力值为$10\times 1+5\times 2+1\times1+2\times2=25$。可以证明这是能让魔导具魔力值最大的选择。

现在碳钾钨会告诉你魔导具和制式法术单元的各个参数，请写一个程序帮忙计算魔导具的魔力值最大是多少。

形式化的说：

给定两个长度分别为 n和 m的字符串 s和 t，以及两个长度分别为 n和 m的数组 a和 b。要求从 s中选取一个子序列，使得该子序列可以由若干个字符串 t重复拼接形成，并且该子序列的价值最大。

子序列的价值定义为子序列中所有字符的贡献和，若 s中的字符 $s_i$被选入子序列且对应 t中的字符$t_j$，则该字符的贡献值为 $a_i \times b_j$。

求该子序列的最大价值。

Input Format

输入共五行 第一行三个整数n、m、K 第二行一个大写字母字符串s 第三行一个大写字母字符串t 第四行n个整数，表示数组a 第五行m个整数，表示数组b

Output Format

一行一个整数，表示魔导具的最大魔法值

Sample

输入1

7 2 5
CCWCKWC
CW
1 10 5 1 100 2 100
1 2

输出1

25

输入2

7 2 3
CAAAKWC
CW
1 10 5 1 100 2 100
1 2

输出2

0

英文想要凑出CW必须要删去AAAK，但是这连续删去的长度大于K=3

Hint

$n,K\leq 10^6,m\leq 10,a_i\leq 2\times 10^5,b_i\leq 10^3$