Xiao D baru-baru ini menemukan sebuah permainan kecil di internet. Aturan permainannya adalah sebagai berikut:

• Tujuan permainan adalah membunuh $n$ naga secara berurutan menurut nomor $1$ sampai $n$. Setiap naga memiliki nilai kesehatan awal $a_i$. Setiap naga juga memiliki kemampuan pemulihan: ketika menggunakannya, nilai kesehatannya bertambah sebesar $p_i$ setiap kali, sampai nilai kesehatannya tidak negatif. Naga hanya mati jika nilai kesehatannya tepat $0$ setelah serangan selesai.
• Pada awal permainan, pemain memiliki $m$ pedang yang kekuatan serangannya diketahui. Setiap kali menghadapi naga, pemain hanya boleh memilih satu pedang. Setelah naga terbunuh, pedang tersebut menghilang, tetapi pemain memperoleh sebuah pedang baru sebagai hadiah.

Xiao D merasa permainan ini sangat membosankan, tetapi pemain yang menyelesaikannya paling cepat dapat memperoleh hak untuk mengikuti ION2018. Karena itu, Xiao D memutuskan untuk menulis sebuah robot bodoh yang akan membantunya menyelesaikan permainan. Robotnya mengikuti aturan berikut:

• Setiap kali menghadapi naga, robot memilih pedang dengan kekuatan serangan terbesar di antara pedang yang dimilikinya saat itu yang kekuatan serangannya tidak melebihi kesehatan awal naga. Jika tidak ada pedang seperti itu, robot memilih pedang dengan kekuatan serangan terkecil.
• Untuk setiap naga, robot menggunakan pedang yang dipilih pada langkah sebelumnya untuk menyerang naga sebanyak $x$ kali yang tetap, sehingga kesehatan naga berkurang sebesar $x \times ATK$.
• Setelah itu, naga terus menggunakan kemampuan pemulihannya, memulihkan $p_i$ kesehatan setiap kali. Jika kesehatannya $0$ sebelum menggunakan kemampuan pemulihan atau setelah salah satu pemulihan, naga mati dan pemain melewati tahap tersebut.

Jelas bahwa jumlah serangan robot adalah kunci untuk menentukan apakah permainan dapat diselesaikan secepat mungkin. Xiao D kini mengetahui semua atribut setiap naga dan ingin mengujimu: berapakah jumlah serangan $x$ yang harus ditetapkan untuk robot agar permainan dapat diselesaikan dengan jumlah serangan sesedikit mungkin?

Jika permainan tidak dapat diselesaikan berapa pun nilai yang ditetapkan, cukup keluarkan $-1$.

Masukan

Baca data dari berkas dragon.in.

Baris pertama berisi sebuah bilangan bulat $T$, yang menyatakan banyaknya kasus uji.

Berikutnya terdapat $T$ kasus uji, masing-masing terdiri dari 5 baris.

• Baris pertama setiap kasus uji berisi dua bilangan bulat $n$ dan $m$, yang menyatakan banyaknya naga dan banyaknya pedang awal;
• Baris berikutnya berisi $n$ bilangan bulat positif; bilangan ke-$i$ menyatakan kesehatan awal $a_i$ naga ke-$i$;
• Baris berikutnya berisi $n$ bilangan bulat positif; bilangan ke-$i$ menyatakan kemampuan pemulihan $p_i$ naga ke-$i$;
• Baris berikutnya berisi $n$ bilangan bulat positif; bilangan ke-$i$ menyatakan kekuatan serangan pedang yang diperoleh sebagai hadiah setelah membunuh naga ke-$i$;
• Baris berikutnya berisi $m$ bilangan bulat positif, yang menyatakan kekuatan serangan $m$ pedang yang dimiliki pada awalnya.

Keluaran

Tulis keluaran ke berkas dragon.out.

Keluaran terdiri dari $T$ baris.

Baris ke-$i$ berisi sebuah bilangan bulat yang menyatakan jumlah serangan minimum $x$ yang memungkinkan robot menyelesaikan permainan untuk kasus uji ke-$i$. Jika jawabannya tidak ada, keluarkan $-1$.

Contoh

Masukan 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

Keluaran 1

59
-1

Penjelasan

Kasus uji pertama:

• Pada awalnya, kekuatan serangan pedang yang dimiliki adalah $\{1,9,10\}$. Naga pertama memiliki kesehatan $3$, sehingga pedang berkekuatan serangan $1$ dipilih. Sebanyak $59$ serangan menimbulkan $59$ kerusakan, sehingga kesehatan naga menjadi $-56$. Setelah $14$ pemulihan, kesehatannya tepat $0$ dan naga mati.
• Pedang berkekuatan serangan $1$ menghilang, dan sebuah pedang berkekuatan serangan $7$ diambil. Kini kekuatan serangan pedang yang dimiliki adalah $\{7,9,10\}$. Naga kedua memiliki kesehatan $5$, sehingga pedang berkekuatan serangan $7$ dipilih. Sebanyak $59$ serangan menimbulkan $413$ kerusakan, sehingga kesehatan naga menjadi $-408$. Setelah $68$ pemulihan, kesehatannya tepat $0$ dan naga mati.
• Kini kekuatan serangan pedang yang dimiliki adalah $\{3,9,10\}$. Naga ketiga memiliki kesehatan $7$, sehingga pedang berkekuatan serangan $3$ dipilih. Sebanyak $59$ serangan menimbulkan $177$ kerusakan, sehingga kesehatan naga menjadi $-170$. Setelah $17$ pemulihan, kesehatannya tepat $0$ dan naga mati.
• Tidak ada cara untuk menyelesaikan permainan dengan kurang dari $59$ serangan, sehingga jawabannya adalah $59$.

Kasus uji kedua:

• Tidak ada cara yang dapat membunuh naga pertama sekaligus naga kedua, sehingga permainan tidak dapat diselesaikan dan keluarannya adalah $-1$.

Contoh 2

Lihat dragon/dragon2.in dan dragon/dragon2.ans di direktori peserta.

Subtugas

Sifat 1 berarti: untuk setiap $i$, $a_i \le p_i$.

Sifat 2 berarti: $\operatorname{LCM}(p_i) \le 10^6$, yaitu kelipatan persekutuan terkecil semua $p_i$ tidak melebihi $10^6$.

Untuk semua kasus uji, $T \le 5$, kekuatan serangan semua senjata $\le 10^6$, dan kelipatan persekutuan terkecil semua $p_i$ adalah $\le 10^{12}$.

Petunjuk

Hasil antara yang kamu gunakan mungkin sangat besar. Perhatikan tipe variabel yang menyimpan hasil antara.