All Tracks Algorithms Searching Binary Search Problem

Monk and His Birthday Party
Tag(s):

Binary Search, Easy-Medium, Greedy

Problem
Editorial
Analytics

Monk went to a really nice place for celebrating birthday with his friends. He booked an awesome resort for hosting the birthday party. But the resort is very costly so he wants to wrap up the party as soon as possible.

Now, everything apart from dinner has been finished. There are $$N$$ different types of delicious cakes for the dinner. The number of cakes of $$i^{th}$$ type is $$C[i]$$ and each of them weighs $$W[i]$$ units. Now, there are $$M$$ friends of Monk present at the party. Each friend has a certain limit $$L[i]$$ units which denotes his/her maximum eating capacity. In other words, cakes having weight larger than $$L[i]$$ units can't be eaten by $$i^{th}$$ friend. Note that eating capacity has no influence on total weight of cakes eaten by a friend.

Each friend takes one minute of time to eat a cake which is in his limits (i.e. if $$L[i] >= W[j]$$, where $$i$$ is the friend number and $$j$$ is the cake's number). Please note that there is no sharing allowed between friends and each cake should be eaten by a single individual. Also, Monk's friends have to eat full cake in one go. They can't eat a fractional part of any cake. And friends can eat cakes simultaneously as they need to wrap up the party as soon as possible. You need to tell whether it is possible for Monk's friends to eat all the cakes present at the birthday party. If yes, then print the minimum time required to eat all the cakes else print $$-1$$ otherwise.

Input:

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

For each of the test cases, first line contains two space separated integers $$N$$ and $$M$$ denoting the number of different types of cakes present at the party and the number of Monk's friends present at the party respectively.

The next line contains $$M$$ space separated integers denoting the eating capacity of the Monk's friends.

In the third line $$N$$ space separated integers will be given where the $$i^{th}$$ integer corresponds to the weight of $$i^{th}$$ type of cake ,i.e., $$W[i]$$.

The fourth line contains $$N$$ space separated integers where the $$i^{th}$$ integer corresponds to the number of cakes of $$i^{th}$$ type present, i.e., $$C[i]$$.

Output:

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

Constraints:

  • $$1 \le T \le 5$$

  • $$1 \le N, M \le 10^5 $$

  • $$1 \le W[i], C[i], L[i] \le 10^8 $$

SAMPLE INPUT
2
5 5
1 2 3 4 5
1 2 3 4 5
5 4 3 2 1
5 5
1 2 3 4 5
1 2 3 4 6
5 5 5 5 5
SAMPLE OUTPUT
3
-1
Explanation

In the first test case,

Friend $$5$$ can eat $$1$$ cake of weight $$5$$ and $$2$$ cakes of weight $$1$$, Friend $$4$$ can eat $$2$$ cakes of weight $$4$$ & $$1$$ cake of weight $$2$$, Friend $$3$$ can eat $$3$$ cakes of weight $$3$$, Friend $$2$$ can eat $$3$$ cakes of weight $$2$$, Friend $$1$$ can eat $$3$$ cakes of weight $$1$$.

Hence minimum time taken will be $$3$$ minutes.

In the second test case, Cakes having weight $$6$$ cannot be eaten by any of the friends. Hence answer is $$-1$$.

Time Limit: 3.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, 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