Jack is an ambitious bus driver. In his journey driving , he passes through N stations located at position S1,S2,....,SN along the positive X axis. In order to ride the bus at the i-th station , a passenger must pay Ci dollars. You are also given an array D with length N-1 such that D1 represents the distance between station 1 and station 2 in meters . D2 represents the distance bet station 2 and station 3 in meters and so on.
Jack starts his journey at the 1st station at time 0. Your task is to calculate the maximum number of dollars Jack can earn throughout the journey."
each station i has 2 properties :
Pi denoting number of passengers that come to station per second Gi denoting the maximum time a passenger can wait for the bus, but when the passenger enters the bus, he will never leave the bus
NOTE : the bus travels at speed of one meter per second Jack can only stop in the stations (never stops in between) When the bus stops at a specific station , it will take exactly 2 seconds to go again and continue his journey
The bus has infinite capacity (can accomodate aany number of passengers)
Insights : since speed is constant = 1 = d / t , therefore d = t (distance convered = time) except for stops when delaying by 2 sec to go again
Input :
T number of test cases <= 100 Each test case starts with single integer N number of stations second line contains N space separated integers C1,C2,....,CN, Ci <= 10^3 (The Cost of riding the bus at station i) The third line contains N-1 space separated integers D1, D2, .... DN (di<=1e3) (Distance between each two consecutive stations) Fourth line contains N space separated integers P1,P2,...,PN (Pi<=1e3) (Number of passengers per second) Fifth line contains N space separated integers G1,G2,...GN (Gi <=1e3) Maximum time a passenger can wait for a bus (of course if that time elapsed Jack loses the money of that passenger)
Goal / output : For each test case, print the maximum profit Jack can make in dollars.
Example
Input :
1 5 10 12 5 3 2 4 3 2 5 2 4 5 2 3 5 2 1 10 11
Output : 457 dollars D I can't reach at 457 . so I would really appreciate any help.
