题目描述

大胃袋LZ经常去扫荡自助餐厅。他有几个规则：

1. 每次去都要吃 $k$ 种必选菜品
2. 每次吃的菜品总量上限为 $p$
3. 每次每种菜品可以重复吃

给出LZ几次自助餐的菜品总清单，判断这个清单是否合法，如果合法求出吃自助次数的最小、最大值。

输入格式

第一行，一个正整数 $q$，表示数据组数

每组数据第一行，$3$ 个正整数 $n,p,k$，分别表示吃的菜品总种类数、每次吃的数量上限、每次必吃的种类数

接下来 $n$ 行，每行一个字符串 $s_i$，一个正整数 $a_i$，表示菜品 $s_i$ 总共消耗了 $a_i$ 份

接下来 $k$ 行，每行一个字符串 $t_i$，表示每次必吃的菜品

输出格式

$t$ 行结果，如果清单合法，输出吃自助的最小、最大次数，否则输出 -1

输入输出样例

2
3 5 2
menzi 15
huimian 12
chaofan 4
menzi
huimian
3 5 1
menzi 15
huimian 12
chaofan 4
chaofan

7 12
-1

样例 $\tt \#1$说明

以下是最小七次自助的一种方案：

1. 吃了 1 份 menzi，1 份 huimian、3 份 chaofan；
2. 吃了 3 份 menzi，1 份 huimian，1 份 chaofan；
3. 吃了 4 份 menzi，1 份 huimian；
4. 吃了 1 份 menzi，4 份 huimian；
5. 吃了 2 份 menzi，3 份 huimian；
6. 吃了 3 份 menzi，1 份 huimian；
7. 吃了 1 份 menzi，1 份 huimian；

没有比七次更小的方案

数据范围

$1\le k\le n\le 10^5,1\le p\le 2\times 10^5,1\le a_i\le 2\times 10^5,1\le|s_i|,|t_i|\le 10,1\le q\le 100$

$|s_i|$ 表示字符串长度