All Tracks Algorithms Sorting Quick Sort Problem

Panik and his Case
Tag(s):

Easy

Problem
Editorial
Analytics

Panik has the secret document containing the evil plans of Zolo the evil ruler for his city.  Zolo has a device which emits beta rays and on coming in direct contact with these rays, you die. As the machine is a prototype he can only use it once for some duration, but guess what Zolo has N such machines. So Zolo plans to use his various machines during [ X, Y ] interval each machine only once. Panik has 24 hours to to evacuate the city because after that Zolo will personally kill all the remaining people. There are K people in the city and It takes exactly Ai time to evacuate i th person where 1 < i < = K. Panik wants to evacuate the maximum no. of people. Help panik in completing the task.


NOTE:

1.)You can only evacuate the city when all the machines are off otherwise you have to take   cover in any house.

2.) assume that there are houses everywhere so while escorting a person If the rays start  emitting again he can take shelter in any house and continue the journey later.

3.) Only one person can evacuate at a time otherwise Zolo might see if more than one person evacuates a time.

4.) Initial Time =0


INPUT:

The first line contains N K: no. of beta-emitting machines and the population of panik-land

Next N lines contain two integers X Y, denoting the  interval of n-th machine

The Final line contains K integers: the time taken by i th person to evacuate the city


OUTPUT:

Output a single integer containing the maximum no. of people which can evacuate the city.


CONSTRAINTS:

0<=N<=10^3

0<=X<=Y<=86400

X Y are given in seconds

1<=K<=10^5

1<=Ai<=101

SAMPLE INPUT
4 5
345 86400
4535 35345
9 343
1 2
9 1 3 2 5
SAMPLE OUTPUT
3
Explanation

since the beta rays would be active during the given duration, the only intervals we have for evacuation are 0-1, 2-9 and 343 - 345. During the 0-1 interval we can evacuate the 2nd person, during the 2-9 interval we can evacuate the third person and partially evacuate the 5th person and during the 343- 345 interval we can fully evacuate the 5th person. therefore answer is 3. This is 1 possibility, there can be many.

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

Notifications
View All Notifications

?