InternDoor

The fastest way through two assembly lines

Mediumdynamic programming · arraysRead the input, print the output

Reported in interviews at (where)

A factory builds a car in n stations, one after another, and has two assembly lines that each have all n stations. Station j takes a1[j] minutes on line 1 and a2[j] minutes on line 2.

Getting the car onto line 1 at the start takes e1 minutes, onto line 2 e2 minutes. Taking it off after the last station takes x1 minutes from line 1 and x2 from line 2.

After station j (every station but the last), the car can stay on its line for free, or move to the other line for the next station: from line 1 that takes t1[j] minutes, from line 2 t2[j] minutes.

For each factory, find the fewest minutes in which a car can get on, through all n stations and off again.

Input

The first line holds T, the number of tests. Each test is six lines: n; then e1 e2 x1 x2; then the n numbers of a1; then the n of a2; then the n - 1 of t1; then the n - 1 of t2. Stations are listed first to last.

Output

For each test, one line: the fewest minutes through its factory.

Example
Input
2
3
2 4 3 2
7 9 3
8 5 6
2 3
2 1
2
1 1 1 1
1 100
100 1
5
5
Output
23
9
  1. On at line 1 (2) for station 1 (7), across to line 2 (2) for station 2 (5), back to line 1 (1) for station 3 (3), then off (3): 23.
  2. Start on line 1 and pay 5 to switch after station 1: far quicker than either slow station.

Limits

  • 1 <= T <= 100
  • 2 <= n <= 100000
  • the n of all the tests add up to at most 400000
  • every number of minutes is 1 to 10000

Hints

Hint 1

Let f1 be the fastest time to finish station j on line 1, and f2 the same on line 2. Each depends only on the two values for station j - 1.

Hint 2

Station j on line 1 is reached from line 1 for free or from line 2 at the cost of moving: f1 = a1[j] + min(f1, f2 + t2[j - 1]), and the same the other way round. Add the exit times at the end.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.