All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Monk visits Coderland
Tag(s):

Easy, Greedy

Problem
Editorial
Analytics

Monk loves to travel. Since his summer vacation was nearing, he decided to plan a journey to Coderland. Now as Monk is just a competitive programmer, he is always short of money. In order to make this journey happen, he wants to minimize the total travel expenditure.

Journey to Coderland will be through N checkpoints. Checkpoints are numbered from 0 to \(N - 1\). At the start of the journey Monk is present at the checkpoint 0. Also checkpoint \(N - 1\) will lead to Coderland. Each checkpoint has a petrol pump which can be used to fill petrol in the car. Now cost of petrol per litre at different checkpoints is given by array C which has 0-based indexing where \(C[i]\) is the cost per litre of petrol at the \(i^{th}\) checkpoint. Note that there is an infinite amount of supply at each checkpoint and car tank is also of infinite capacity. Now another array L is given which has 0-based indexing where \(L[i]\) denotes the amount of petrol in litres required to reach the \((i + 1)^{th}\) checkpoint from the \(i^{th}\) checkpoint. Note that the extra petrol remaining in the tank does not vanishes after reaching a checkpoint. Also, Monk should have atleast \(L[i]\) litres of petrol at each checkpoint in order to reach the next checkpoint.

Can you help Monk estimate the minimum cost required in order complete the journey?

Input:

First line of the input contains test cases denoted by T.

For each of the test cases, first line contains a single integers N denoting the number of checkpoints.

The next line contains N space separated integers representing the array C which has 0-based indexing where the \(i^{th}\) integer denotes the cost per litre of petrol at \(i^{th}\) checkpoint.

Last line contains array L ,which has 0-based indexing, consisting of N space separated integers where the \(i^{th}\) integer denotes the required amount of petrol needed to reach the \((i+1)^{th}\) checkpoint from the \(i^{th}\) checkpoint.

-Output:

For each of the test cases, output the required answer in a separate line.

Constraints:

  • \(1 \le T \le 5\)

  • \(1 \le N \le 10^5 \)

  • \(1 \le C[i], L[i] \le 10^5 \)

SAMPLE INPUT
1
2
5 1 
1 2
SAMPLE OUTPUT
7
Explanation

We can buy petrol at rate 5 per litre from checkpoint 0 and then at rate 1 per litre from checkpoint 1. Thus, total cost incurred will be \(5 * 1 + 1 * 2 = 7\). Had we bought all the petrol at checkpoint 0, cost incurred would have been \( 5*(1+2) = 15\) which is not the best answer.

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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (CheckPoint III)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?