All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Iron man vs Captain America
Tag(s):

Easy

Problem
Editorial
Analytics

Iron Man and Captain America start for a mission from Isengard to Middle-Earth. There are two different tracks from Isengard to Middle-Earth. Each track has N toll taxes where they have to pay and in between they can change track from any toll but for that they have to pay extra. By changing track from ith toll of first track one can reach (i+1)th toll of second track and vice versa. All you have to calculate is minimum cost required to reach from Isengard to Middle-Earth.

Input

The first line of input contains an integer T, the number of Test Cases.
The second line of input contains an integer N, denoting the number of tolls.
The third line of input contains N space separated integers, denoting the amount to pay at ith toll in first track.
The Fourth line of input contains N space separated integers, denoting the amount to pay at ith toll in second track.
The Next line of input contains N-1 space separated integers, denoting the amount to pay on changing track from ith toll of first track to (i+1)th toll in second track.
The Next line of input contains N-1 space separated integers, denoting the amount to pay on changing track from ith toll of second track to (i+1)th toll of first track.

Output

Output of each testcase will consist of a single integer denoting minimum cost required for bike trip from Leh to Ladakh.

Constraints

1 <= T <= 100
1 <= N <= 100000
1 <= Amount to pay at any point <= 100000

SAMPLE INPUT
2
2
15 6 
5 21 
1 
7 
3
7 2 5 
5 2 4 
7 6 
2 2
SAMPLE OUTPUT
18
11
Explanation

Sample case 1 :- path of minimum cost will be 1st toll of second track --> 2nd toll of first track.total amount = 5 + 7 + 6 = 18. Here 7 is extra amount to pay on changing track from 1st toll of second track to 2nd toll of first track.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NIT Surat

Challenge Name

Epiphany 6.1

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications