小D descobriu recentemente um pequeno jogo na Internet. As regras do jogo são as seguintes:

• O objetivo é matar $n$ dragões, por ordem dos seus números de $1$ a $n$. Cada dragão tem uma quantidade inicial de pontos de vida $a_i$. Cada dragão também tem uma capacidade de regeneração: quando a utiliza, os seus pontos de vida aumentam em $p_i$ de cada vez, até se tornarem não negativos. Só morre depois de terminarem os ataques, quando os seus pontos de vida forem exatamente $0$.
• No início do jogo, o jogador possui $m$ espadas com poderes de ataque conhecidos. Ao enfrentar cada dragão, só pode escolher uma espada. Depois de matar o dragão, essa espada desaparece, mas o jogador recebe uma espada nova como recompensa.

小D acha este jogo muito aborrecido, mas o jogador que o terminar mais depressa ganha o direito de participar na ION2018. Por isso, 小D decidiu programar um robô simples para a ajudar a terminar o jogo. O robô que programou segue estas regras:

• Sempre que enfrenta um dragão, o robô escolhe, entre as espadas que possui e cujo poder de ataque não excede os pontos de vida iniciais do dragão, a que tem maior poder de ataque. Se não houver nenhuma espada nessas condições, escolhe a que tem menor poder de ataque.
• Contra cada dragão, o robô utiliza a espada escolhida no passo anterior para o atacar um número fixo de vezes, $x$, reduzindo os pontos de vida do dragão em $x\times ATK$.
• Depois disso, o dragão utiliza repetidamente a sua capacidade de regeneração, recuperando $p_i$ pontos de vida de cada vez. Se os seus pontos de vida forem $0$ antes de utilizar essa capacidade ou depois de alguma regeneração, o dragão morre e o jogador passa este nível.

Assim, é evidente que o número de ataques do robô é a chave para determinar se consegue terminar o jogo o mais depressa possível. 小D conhece agora todos os atributos de cada dragão e quer pôr-te à prova: sabes que valor deve atribuir ao número de ataques $x$ do robô para terminar o jogo com o menor número de ataques?

Naturalmente, se nenhum valor permitir terminar o jogo, basta apresentar -1.

Entrada

Lê os dados do ficheiro dragon.in.

A primeira linha contém um inteiro $T$, que representa o número de casos de teste.

Seguem-se $T$ casos de teste, cada um composto por 5 linhas.

• A primeira linha de cada caso contém dois inteiros, $n$ e $m$, que representam o número de dragões e o número inicial de espadas;
• A linha seguinte contém $n$ inteiros positivos; o $i$-ésimo é o número inicial de pontos de vida $a_i$ do $i$-ésimo dragão;
• A linha seguinte contém $n$ inteiros positivos; o $i$-ésimo representa a capacidade de regeneração $p_i$ do $i$-ésimo dragão;
• A linha seguinte contém $n$ inteiros positivos; o $i$-ésimo representa o poder de ataque da espada recebida como recompensa por matar o $i$-ésimo dragão;
• A linha seguinte contém $m$ inteiros positivos, que representam os poderes de ataque das $m$ espadas possuídas inicialmente.

Saída

Escreve a saída no ficheiro dragon.out.

Apresenta $T$ linhas no total.

A linha $i$ deve conter um inteiro: o menor número de ataques $x$ que permite ao robô terminar o jogo no $i$-ésimo caso de teste. Se não existir resposta, apresenta -1.

Exemplos

Entrada 1

2
3 3
3 5 7
4 6 10
7 3 9
1 9 1000
3 2
3 5 6
4 8 7
1 1 1
1 1

Saída 1

59
-1

Explicação do exemplo 1

Primeiro caso de teste:

• Inicialmente, os poderes de ataque das espadas são $\{1,9,10\}$. O primeiro dragão tem $3$ pontos de vida, pelo que se escolhe a espada com poder de ataque $1$. Atacando $59$ vezes, causam-se $59$ pontos de dano e os pontos de vida do dragão tornam-se $-56$. Depois de regenerar $14$ vezes, os seus pontos de vida são exatamente $0$ e ele morre.
• A espada com poder de ataque $1$ desaparece e obtém-se uma espada com poder de ataque $7$. Os poderes de ataque das espadas são agora $\{7,9,10\}$. O segundo dragão tem $5$ pontos de vida, pelo que se escolhe a espada com poder de ataque $7$. Atacando $59$ vezes, causam-se $413$ pontos de dano e os pontos de vida do dragão tornam-se $-408$. Depois de regenerar $68$ vezes, os seus pontos de vida são exatamente $0$ e ele morre.
• Os poderes de ataque das espadas são agora $\{3,9,10\}$. O terceiro dragão tem $7$ pontos de vida, pelo que se escolhe a espada com poder de ataque $3$. Atacando $59$ vezes, causam-se $177$ pontos de dano e os pontos de vida do dragão tornam-se $-170$. Depois de regenerar $17$ vezes, os seus pontos de vida são exatamente $0$ e ele morre.
• Não existe forma de terminar o jogo com menos de $59$ ataques, pelo que a resposta é $59$.

Segundo caso de teste:

• Não existe forma de matar tanto o primeiro como o segundo dragão, pelo que não se pode terminar o jogo. A saída é -1.

Exemplo 2

Consulta os ficheiros dragon/dragon2.in e dragon/dragon2.ans no diretório dos concorrentes.

Subtarefas

A propriedade 1 significa que, para qualquer $i$, $a_i\le p_i$.

A propriedade 2 significa que $\operatorname{LCM}(p_i)\le 10^6$, isto é, o mínimo múltiplo comum de todos os $p_i$ não excede $10^6$.

Para todos os testes, $T\le 5$, o poder de ataque de todas as armas é $\le 10^6$, e o mínimo múltiplo comum de todos os $p_i$ é $\le 10^{12}$.

Dica

Os resultados intermédios que utilizares podem ser muito grandes. Presta atenção ao tipo das variáveis em que os guardas.