All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

AltF4 and HackerEarth's Problem Setting
Tag(s):

Hard

Problem
Editorial
Analytics

There are lots of contest coming up on HackerEarth and it is in urgent need of lots of problems. So it calls a meeting of all the problem setters in the team.

There are N problem setters in HackerEarth. Everybody has a fixed price for preparing a problem. This is given by the array prices[ ] and all elements of the array are distinct. Obviously the higher charged setters are more experienced and can easily do the task assigned to its lower charged setters.

The contest moderator AltF4, assigns a certain number of tasks to each of the setter. This is given by the array tasks[ ]. The finance team calculates the total cost to the company as sum of price[i] * tasks[i] for all i.

This was simple. But the setters have now grown greedy. They need extra incentives to meet their busy schedule, transportation and accommodation costs. So everybody decides that if HackerEarth needs them and invites them to create problems, they would charge for extra K tasks to meet these surcharges.

For example if N = 2, prices of the setters are {10, 50} and AltF4 needs tasks from both as {10, 20} the cost to company would have been 10 x 10 + 50 x 20 = 1100. With the new law of surcharges with K = 10, there are 2 possibilities.

  1. 1st setter does 10 tasks and 2nd setter does 20 tasks. Cost is 10 x 20 + 50 x 30 = 1700.
  2. 2nd setter does all 30 tasks. Cost is 50 x 40 = 2000.
In this case it is better to invite both the setters and do their tasks. Note that 1st setter cannot do the tasks of the 2nd setter because he is not that much experienced (lesser price).

However, if K would have been 50, then analyzing the two possiblities:

  1. 1st setter does 10 tasks and 2nd setter does 20 tasks. Cost is 10 x 60 + 50 x 70 = 4100.
  2. 2nd setter does all 30 tasks. Cost is 50 x 80 = 4000.
In this case it is better to invite only the 2nd setter and let him do the tasks of the 1st setter as well.

Given the N, K, and the arrays prices[ ] and tasks[ ], your job is the help the finance team calculate the minimum cost possible for the company for doing all tasks.

Input & Output:

The first line contains the number of test cases T. The first line of every test case contains two integers N K separated by space. The next two lines contains the arrays prices and tasks respectively. All numbers are space separated.

For each test case, output the minimum possible cost to the company and help the finance team.

Constraints:
T ≤ 25
1 ≤ N, prices[i], tasks[i] ≤ 2000
0 ≤ K ≤ 2000

SAMPLE INPUT
2
2 10
10 50
10 20
2 50
10 50
10 20
SAMPLE OUTPUT
1700
4000
Explanation

Provided in the problem statement.

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: Bash, 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, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Rain

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?