All submissions for this problem are available.
Chef Po had recently started home delivery service for pizzas. Po has only a single delivery boy that delivers the orders by riding his motorcycle. The motorcycle has an unlimited capacity of fuel tank. However, it is too old and can only ride 1 km for each 1 liter of fuel.
There are N fuel stations near the restaurant. The i-th fuel station can fill a fuel tank exactly Ki liters; not more and not less. Filling a fuel tank with any amount of fuel in those stations tends to take a long time. Since the fuel stations are placed near the restaurant, no fuel is needed to go to a fuel station.
Today Chef Po received N pizza orders, which is the same number of fuel stations fortuitously. The house of the person that ordered the i-th order is Hi km away from the restaurant. The delivery boy cannot deliver more than one order at a time. Therefore, after delivering an order, he must return back to the restaurant to take the next order.
The delivery boy is an efficient person and thus he wants to fill the fuel tank with the exact amount of fuel required to deliver an order and return back. He also does not want to spends much time filling the tank, so he wants to minimize the number of times he fills the tank. Help him determine the minimum number of times he must fill the tank to deliver all orders.
The first line contains a single integer T denoting the number test cases. The description of T test cases follows. For each test case, the first line contains a single integer N. The second line contains N space-separated integers Hi. The third line contains N space-separated integers Ki.
For each test case, output a single line containing the minimum number of times the delivery boy must fill the tank.
1 ≤ T ≤ 500
1 ≤ N ≤ 500
1 ≤ Hi ≤ 500
1 ≤ Ki ≤ 500
There is at least one way for completing the deliveries.
That is, the delivery boy always can fill a fuel tank exactly 2 * Hi liters for 1 ≤ i ≤ N.
Input: 1 4 1 2 3 4 1 4 5 3 Output: 7
Here is one possible solution.
For the first order, the delivery boy must ride 1 + 1 = 2 km long. Fill the tank twice in the first fuel station.
For the second order, the delivery boy must ride 2 + 2 = 4 km long. Fill the tank once in the second fuel station.
For the third order, the delivery boy must ride 3 + 3 = 6 km long. Fill the tank twice in the fourth fuel station.
For the fourth order, the delivery boy must ride 4 + 4 = 8 km long. Fill the tank in the third and fourth fuel stations.
In total, the delivery boy must fill the tank 7 times. There is no way to fill the tank less than 7 times.
|Tags||dec12, dynamic-programming, khadarbasha, simple|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.