위처의 물약

신화 속 세계에서 격투 대회가 열린다. 참가자는 괴물을 한 마리씩 상대하고, 자신이 쓰러질 때까지 최대한 많은 괴물을 쓰러뜨려야 한다. 위처 부족은 다른 부족보다 유리하다. 기력을 올려 주지만 독이 든 물약을 마시기 때문이다. 물약은 기력을 즉시 올려 주고, 기력이 남아 있는 한 위처는 쓰러지지 않는다. 다만 독 때문에 물약은 괴물을 한 마리 쓰러뜨린 직후에 한 병까지만 마실 수 있다.

전설의 위처 게롤트는 물약 $N$병을 들고 대회에 나선다. $i$번 병의 강도는 $E_i$, 독성은 $P_i$이다. 이 병을 마시면 기력이 $E_i$만큼 오르지만 기력은 100을 넘지 않는다. 동시에 혈중 독성이 $P_i$만큼 오른다. 혈중 독성이 100에 도달하면 게롤트는 쓰러지므로, 그렇게 되는 병은 절대 마시지 않는다.

게롤트의 몸은 시간이 지나면서 독을 빠르게 배출한다. $T$분이 지나면 혈중 독성이 $T$만큼 내려가고, 0 아래로는 내려가지 않는다. 그래서 뒤에 다른 병을 안전하게 마실 수 있다.

괴물은 모두 같다. 한 마리를 쓰러뜨리는 데 기력 $K$와 시간 $M$분이 든다. 게롤트의 기력이 $K$ 이하이면 괴물을 쓰러뜨릴 수 없고, 대회는 거기서 끝난다.

게롤트는 기력 100, 혈중 독성 0으로 시작한다. 물약 자료와 괴물 자료를 분석해서 게롤트가 쓰러뜨릴 수 있는 괴물의 최대 수를 구하라.

첫 줄에 테스트 케이스의 수 $C$가 주어진다 ($1 \le C \le 20$). 각 테스트 케이스는 네 줄로 이루어진다.

• 첫째 줄: 괴물 한 마리에 드는 기력 $K$와 시간 $M$ ($10 \le K \le 80$, $1 \le M \le 100$)
• 둘째 줄: 게롤트가 가진 물약 병의 수 $N$ ($1 \le N \le 8$)
• 셋째 줄: 1번부터 $N$번 병의 강도 $E_1, E_2, \dots, E_N$ ($1 \le E_i \le 100$)
• 넷째 줄: 1번부터 $N$번 병의 독성 $P_1, P_2, \dots, P_N$ ($1 \le P_i \le 100$)

각 테스트 케이스마다 게롤트가 쓰러뜨릴 수 있는 괴물의 최대 수를 한 줄에 하나씩 출력한다.

게롤트는 물약이 남아 있어도 괴물을 쓰러뜨린 뒤에 마시지 않고 넘어갈 수 있다. 각 병은 한 번만 마신다. 남은 병이 없거나 마시지 않기로 하면 남은 기력만으로 계속 싸운다.

한 번의 전투는 순서가 정해져 있다. 기력 $K$와 시간 $M$분을 써서 괴물을 쓰러뜨리고, 혈중 독성이 $M$만큼 내려간 다음 (0 아래로는 내려가지 않는다), 그 뒤에야 물약 한 병을 마실 수 있다.