After spending quality time outdoors, Kevin has decided to start looking at ways he can upskill and get a job again. He's received several suggestions such as reading the Cracking the Coding Interview, reading The Algorithm Design Manual, practicing LeetCodes, and also participating in AUCPL!

He decides that from 9 am to 9 pm, he will commit to studying, while taking breaks in between. Breaks can only be scheduled between study tasks, but they must be taken as soon as possible. If a study task or break goes beyond 9 pm, that task will not be taken.

Every day, he plans out his day with a list of study tasks that he'll do, and also some breaks. He prioritises some tasks over others, adjusting them each day as needed. If two tasks have the same priority, they should be scheduled based on which task has a longer duration.

Can you help Kevin plan out his schedule?

Input

The first line contains two integers ~s~ and ~b~ ~(1 \leq b \leq s \leq 20)~, the number of study tasks and breaks.

The next ~s~ lines contain two integers ~d~ and ~p~ ~(1 \leq p \leq 100)~, the duration and priority of that task.

The next ~b~ lines contain a single integer ~d~, the duration of the break.

The duration ~d~ ~(1 \leq d \leq 720)~ is given in minutes.

Output

Output the total minutes Kevin would spend studying and the total minutes he would spend taking breaks.

Clarifications

• You may have two consecutive study tasks if there are no more breaks remaining. However, you cannot have two consecutive breaks.

Example

Input 1

3 2
60 10
30 5
50 8
15
20

Output 1

140 35

• Kevin first studies for ~60~ minutes, since this has the highest priority of ~10~.
• He then takes a mandated study break for ~15~ minutes, since he wants to take breaks that take less time first.
• He continues studying for a further ~50~ minutes since he tackles the next-highest priority task (with a priority of ~8~).
• He takes another break for ~20~ minutes.
• He completes his remaining task which takes ~30~ minutes.

In total, he has spent ~140~ minutes studying and ~35~ minutes taking a break.

Input 2

2 1
600 2
100 1
200

Output 2

600 0

Kevin can only study for $600$ minutes. He cannot take a break since it would go past 9 pm if he did so, and he can't squeeze in another study task since he has a mandated break (which he cannot take).