C. USD vs Liras
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Omar borrowed some money from his loyal and rich friend Rajaei. After successful trading, Omar now has $$$m$$$ dollars and an infinite amount of Liras. He wants to repay his debt to Rajaei over $$$n$$$ days.

You are given two arrays:

  • Array $$$a$$$ of size $$$n$$$, where $$$a_i$$$ represents the amount of dollars Rajaei demands from Omar on day $$$i$$$.
  • Array $$$b$$$ of size $$$n$$$, where $$$b_i$$$ represents the exchange rate of 1 dollar to Liras on day $$$i$$$.
Then Omar has two ways to repay the money on day $$$i$$$, let $$$c_i$$$ be the amount of liras Omar pays on day $$$i$$$.
  1. Pay $$$a_i$$$ dollars directly. There $$$c_i = 0$$$.
  2. Pay $$$x$$$ dollars $$$(0 \le x \le a_i)$$$, and cover the remaining $$$(a_i - x)$$$ dollars in liras at the exchange rate $$$b_i$$$.This means he will pay $$$c_i = (a_i - x) \times b_i$$$ liras on day $$$i$$$.

Find the minimum value $$$y$$$ such that $$$max(c_1,\space c_2, \dots,\space c_n) \le y$$$ and Omar can repay his debt using his dollars and liras.

Input

The first line of the input contains a single positive integer $$$t$$$ $$$(1 \le t \le 10^5)$$$, the number of test cases.

The first line of each test case contains two positive integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 3 \times 10^5)$$$ $$$(1 \le m \le 10^9)$$$, the number of days and the amount of dollars Omar has.

The second line of each test case contains $$$n$$$ positive integers $$${a_1, \space a_2, \dots, \space a_N}$$$ $$$(1 \le a_i \le 10^9)$$$.

The third line of each test case contains $$$n$$$ positive integers $$${b_1, \space b_2, \dots, \space b_N}$$$ $$$(1 \le b_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ overall test cases doesn't exceed $$$3 \times 10^5$$$.

Output

For each test case output the minimum value $$$y$$$ such that $$$max(c_1,\space c_2, \dots,\space c_N) \le y$$$ and Omar can repay his debt using his dollars and liras.

Example
Input
1
6 23
1 8 2 2 5 10
7 3 8 2 2 3
Output
4