7523: [CSES Problem Set] Factory Machines
[Creator : ]
Description
A factory has $n$ machines which can be used to make products. Your goal is to make a total of tt products.
For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.
What is the shortest time needed to make tt products?
For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.
What is the shortest time needed to make tt products?
Input
The first input line has two integers $n$ and $t$: the number of machines and products.
The next line has $n$ integers $k_1,k_2,\dots,k_n$: the time needed to make a product using each machine.
The next line has $n$ integers $k_1,k_2,\dots,k_n$: the time needed to make a product using each machine.
Output
Print one integer: the minimum time needed to make $t$ products.
Constraints
$1≤n≤2⋅10^5$
$1 \le t \le 10^9$
$1 \le k_i \le 10^9$
$1 \le t \le 10^9$
$1 \le k_i \le 10^9$
Sample 1 Input
3 7
3 2 5
Sample 1 Output
8
Machine 1 makes two products, machine 2 makes four products and machine 3 makes one product.