题目内容

小塔正在游戏中进行一次有趣的探险，他第$0$天结束后在起点$0$位置，要安排接下来$1$~$t$天的行程、初始时每天最多可以选择前进$K$格。

沿途有一些特定的位置$x[i]$，在这些位置上小塔可以选择停下来获取增强，并且今天不再继续行进，可以使得之后每天能多行走$y[i]$格(也可以途径时不停下，选择继续进行今日的行程，但不会获得增强)。

一个位置可能有多个增强，小塔只能选择其中一个获得，即使再多停留一天也不能获得其他的增强效果。

小塔想知道在$t$天后，他最多能走到哪一位置。

输入描述

第一行$1$个整数$T$，表示数据组数。

对于每组数据:

第一行包含三个整数$K$、$t$和$N$，分别表示初始每天最多前进的格数、总天数以及可以获得增强的位置的数量。

第二行包含$N$个整数$x[1],x[2],...,x[N]$。

第三行包含$N$个整数$y[1],y[2],...,y[N]$。

其中$x[i],y[i]$分别是第$i$个可以获得增强的位置以及增强的强度。

$1≤T≤5,0≤t≤100,1≤N≤50,1≤x[i],y[i],K≤50$

输出描述

输出$T$行分别表示每组数据答案。

对每组数据，输出一行一个整数，表示在$t$天后，小塔能够到达的最远位置。

样例1

输入

2
3 5 2
2 5
2 1
1 0 1
1
1

输出

23
0

提示

对于第一组样例:

初始状态下，小塔每天可以前进最多$'3'$格。

第一天，小塔前进到$'2'$位置，接着停在$'2'$位置获取$'2'$格增强，使得他之后每天最多可以前进$'5'$格。

第二天，小塔前进到$'5'$位置，停在那获得$'1'$格增强，之后他每天最多行进$'6'$格。

第$3、4、5$天小塔均全速行进，每天前进$6$格。

在$'T=5'$天后，小塔可以利用增强前进到$'23'$位置。

对于第二组样例:

小塔的角色索性不走了，只走$0$天，由题面，他第$0$天结束后的位置就是位置$0$，所以答案就是$0$。