Witcher Potion

In a mythical world there is a fighting contest. Each contestant faces monsters one at a time and defeats as many as possible before being knocked out. The Witcher tribe has an edge over the others, because a Witcher drinks energy potions that are also poisonous. A potion raises energy at once, and a Witcher is never knocked out while energy remains. The poison limits how often a potion helps: a Witcher may drink at most one bottle right after defeating a monster.

Geralt, a legendary Witcher, enters the tournament with $N$ potion bottles. Bottle $i$ has strength $E_i$ and toxicity $P_i$. Drinking it raises his energy by $E_i$ units, but energy never rises above 100. It also raises the toxicity in his blood by $P_i$ units. If blood toxicity reaches 100 Geralt is knocked out, so he never drinks a bottle that would take it that far.

His body clears poison quickly. In $T$ minutes blood toxicity drops by $T$ units, and it never falls below 0. That is what lets him safely drink another bottle later on.

All monsters are the same. Defeating one costs $K$ energy units and takes $M$ minutes. If Geralt has $K$ or fewer energy units he cannot defeat a monster, and the contest is over for him.

Geralt starts with 100 energy units and 0 blood toxicity. Analyse the potion data and the monster data, then report the largest number of monsters Geralt can defeat.

The first line contains the number of test cases $C$ ($1 \le C \le 20$). Each test case is given on four lines.

• Line 1: $K$ and $M$, the energy and the time Geralt spends on each monster ($10 \le K \le 80$, $1 \le M \le 100$)
• Line 2: $N$, the number of potion bottles Geralt carries ($1 \le N \le 8$)
• Line 3: $E_1, E_2, \dots, E_N$, the strength of bottles 1 to $N$ ($1 \le E_i \le 100$)
• Line 4: $P_1, P_2, \dots, P_N$, the toxicity of bottles 1 to $N$ ($1 \le P_i \le 100$)

For each test case print the largest number of monsters Geralt can defeat, one line per case.

Geralt may skip the potion after defeating a monster even when bottles are left in his inventory. Each bottle is drunk at most once. When no bottle is left, or when he chooses not to drink, he fights on with the energy he still has.

One fight follows a fixed order. He spends $K$ energy and $M$ minutes to defeat the monster, his blood toxicity drops by $M$ units (never below 0), and only after that may he drink one bottle.