给定一个长度为 $n$ 的由小写英文字母组成的字符串 $s$ 和一个非递减数组 $\{v_1, v_2, \dots, v_n\}$。

一个非空字符串集合 $T$ 被称为“好的”，当且仅当： * $T$ 中不存在一对字符串，使得其中一个是另一个的后缀。在此处，若字符串 $A$ 可以通过删除字符串 $B$ 开头的若干字符（可能为零）得到，则称 $A$ 是 $B$ 的一个后缀。

对于一个好的集合 $T$，定义 $T$ 的价值为 $\sum_{t \in T} v_{|t|}$，其中 $|t|$ 是字符串 $t$ 的长度。

对于一个字符串 $t$ 和某个正整数 $k$，定义 $f(t, k)$ 为满足以下条件的所有好的集合 $T$ 中的最大价值： $|T| \le k$； $T$ 中的字符串均为 $t$ 的子串。在此处，若字符串 $A$ 可以通过删除字符串 $B$ 开头的若干字符（可能为零）和结尾的若干字符（可能为零）得到，则称 $A$ 是 $B$ 的一个子串。

你需要回答 $q$ 次询问。对于每次询问，给定两个值 $l, k$ ($1 \le l \le n, 1 \le k \le 10^9$)，你需要求出 $f(s[1, l], k)$，其中 $s[1, l]$ 表示 $s$ 的前 $l$ 个字符组成的子串。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ —— 测试用例的数量。接下来是 $T$ 个测试用例的描述。 每个测试用例的第一行包含两个整数 $n, q$ ($1 \le n, q \le 2 \times 10^5$) —— 字符串 $s$ 的长度和询问次数。 第二行包含字符串 $s$。 第三行包含 $n$ 个正整数 $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 10^9$)。保证 $v_1 \le v_2 \le \dots \le v_n$。 接下来的 $q$ 行，每行包含两个正整数 $l, k$ ($1 \le l \le n, 1 \le k \le 10^9$)，描述一个询问。

保证 $T \le 20, \sum q \le 10^6, \sum n \le 10^6$。

输出格式

对于每个询问，输出一个整数表示答案。

样例

输入格式 1

2
8 3
ababaaab
1 2 2 5 7 8 10 10
8 1
1 2
4 4
6 2
abcacb
4 7 9 10 13 49
4 2
6 3

输出格式 1

10
1
7
19
72