Little Joseph a car manufacturer and he wants to assemble a car in the fastest time possible.
His company has two assembly lines that will bring a chasis into all the different stages of production and finally come out as a car. This is seen in the diagram above.
However, there are some stages of production in which assembly line 1 is faster than assembly line 2, and yet other stages in which it's the other way round. However, to switch between assembly lines takes time for the other assembly team to know what the other assembly line has done etc, and hence there's a time cost when we switch between the assembly lines (e.g. shown as t11, denoting moving from Assembly Line 1 after the first stage of production to Assembly Line 2 for the second stage of production)
Even sending the chassis from the warehouse to the assembly lines needs time (e1 being the time to bring the chasis into Assembly Line 1) as well as sending the finished product back to the warehouse (x1 being the time to bring the car from Assembly Line 1 back into the warehouse).
Given all these values, what is the minimum time to assemble the car?
The first line contains of the integer n representing the number of stages in production
The second line contains two integers e1 and e2.
The third line contains n integers, the time taken for Assembly 1 to finish that stage of production
The fourth line contains n integers, the time taken for Assembly 2 to finish that stage of production
The fifth line contains n - 1 integers, the time taken to transfer from Assembly Line 1 to Assembly Line 2 after the k-th stage (t1,k)
The sixth line contains n - 1 integers, the time taken to transfer from Assembly Line 2 to Assembly Line 1 after the k-th stage (t2,k)
The seventh line contains two integers x1 and x2.
A single integer representing the minimum units of time taken to assemble the car.
For 30% of the test cases, n < 100.
For 60% of the test cases, n < 1000.
For 100% of the test cases, n < 10000.
2 3 4 19 20
7 8 9 1 2
1 1 1 1
1 1 1 1
The optimum way is to go through Assembly Line 1 first(with cost of 2), go through the first three stages of production (with cost of 2 + 3 + 4 = 9), then transfer to Assembly Line 2 (with cost of 1), and go through the last two stages in Assembly Line 2 (with cost of 1 + 2 = 3), and exit Assembly Line 2 (with cost of 10).
This will give us a total cost of 25.