MYQ6 - Serve The Street

no tags 


Shree is a very ambitious person and wants to start a new company "RAM COURIER SERVICE" in the country of Thuvax. He plans to open his first office in the Main Street of Thuvax to serve only the people of this street. The Main Street is an inclined road consisting of N buildings spaced out unevenly(building 1 at lowest level and building N at highest level). The distance between adjacent buildings are known to Shree.
 
The delivery costs incurred by him for various deliveries are calculated as follows:
 
To deliver a package of weight 'w' to a building downhill at a distance 'd' from the office, Shree spends w*d*1 units of money.
To deliver a package of weight 'w' to a building uphill at a distance 'd' from the office, Shree spends w*d*2 units of money.
To deliver a package of non-zero weight to his own building, Shree spends 10 units of money irrespective of the weight of the package.
 
Shree being an astute businessman wants to choose one of these buildings for his new office so that the total delivery cost incurred by him is minimum.
Help Shree choose the building for his new office.

Input

The first line of the input consists of number of test cases t(1<=t<=20)
 
The first line of each test case consists of a single number N(1<=N<=10^6) which is the number of buildings in the main street.
The next line contains N integers representing the weight to be delivered at ith (1<=i<=N) building (0<=w[i]<=100).
The last line contains N-1 integers where the ith (1<=i<=N-1) integer represents the distance between i and i+1 th building(1<=d[i]<=100).

Output

Output a single line for each test case containing two integers separated by a space.
The first integer is the minimum delivery cost and the next integer is the building number where the office should be placed in order to incur that cost.  
If more than one building has the same minimum cost, print the building labelled with the smallest number.

Example

Input:
1 
5
1 2 3 4 5
1 1 1 1 Output: 30 4

hide comments
vengatesh15: 2017-01-27 10:57:15

did in O(n) take care for weight as 0 that case me 1 WA.

Last edit: 2017-01-27 10:59:04
Liquid_Science: 2016-02-26 18:10:35

I won't lie ,took me 2 hours to do this in O(n)[ i know i know :( ] but then AC in one go :)

Pranav Rai: 2015-09-11 23:19:26

Stuck on this problem , getting a TLE with O(n) ?
http://www.spoj.com/submit/MYQ6/id=15114853
Admin - any tricky test cases , or some hint

EDIT: For the worst case [t=20 , n=10^6 , and all values 100] my Answer is coming out to be 3333333333330010 666667

Last edit: 2015-09-12 06:39:34
ankurcent: 2015-05-04 05:09:41

is O(n^2) a bad time limit?

Shubham: 2012-08-18 05:01:30

don't read till EOF.. I have got AC and those getting WAs might want to check when n=1 as a special case.

BOND: 2012-08-09 22:12:36

read till EOF ...

Last edit: 2012-08-10 09:56:28
Aman Kumar: 2012-08-05 20:06:49

take care of long long too, in addition to the comments below..

Last edit: 2012-08-05 20:07:18
15972125841321: 2012-06-18 21:32:47

that 10 cost me 7 wa ...

:D: 2012-05-11 17:39:50

Yes, delivering package of weight zero ALWAYS costs 0.

Divanshu: 2012-05-11 11:45:37

What is the cost for delivering zero weight package in the building itself? zero?


Added by:jack(chakradarraju)
Date:2012-02-14
Time limit:0.103s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2012