### Woburn Challenge 2015-16 Round 4 - Junior Division

## Problem 4: Target Practice

In between missions, Bond makes sure to keep his trigger finger in shape. Today, he's hitting the firing range at MI6 headquarters.

His target consists of `N` (1 ≤ `N` ≤ 10^{5}) concentric rings drawn on a piece of graph paper, centered at the origin. The rings are numbered 1 to `N` from smallest to largest, with the `i`-th ring having an outer radius of `R _{i}` (1 ≤

`R`<

_{1}`R`< … <

_{2}`R`< 10

_{N}^{9}). Each ring includes its outer radius, but not its inner radius – for example, if a bullet hits exactly

`R`units away from the origin, then it's considered to land inside ring

_{i}`i`, but if it's slightly further away, then it instead lands inside ring

`i`+ 1. If a shot strikes no further than

`R`units away from the origin, then it naturally lands inside ring 1. The

_{1}`i`-th ring is worth

`P`(1 ≤

_{i}`P`≤ 1000) points if it's hit.

_{i}Bond has fired `M` (1 ≤ `M` ≤ 10^{6}) shots at the target, with the ith one striking at coordinates (`X _{i}`,

`Y`) (−10

_{i}^{9}≤

`X`,

_{i}`Y`≤ 10

_{i}^{9}), and is now waiting to be notified of his total score. Each shot will be awarded points based on which ring it landed in, except for shots which landed strictly outside the outer radius of ring

`N`, which will receive 0 points.

Q is in charge of tallying up the points, but he's decided to play a little trick on Bond – rearranging the rings' point values! Given that he may permute the values `P`_{1..N} in any way he'd like before computing and adding up the `M` shots' scores, he's wondering how small or large Bond's total score could possibly end up being. After the stunt Bond pulled last week with taking Q's brilliant new automobile for a little unauthorized test drive, and promptly causing it to internally combust (and not in a good way), we can only imagine whether Q will choose to give Bond the smallest or largest possible score... However, in any case, can you please help him determine both of these values?

### Subtasks

In test cases worth 6/40 of the points, `N` ≤ 10 and `M` ≤ 20.

In test cases worth another 10/40 of the points, `N` ≤ 800 and `M` ≤ 400.

In test cases worth another 12/40 of the points, `N` ≤ 10^{5} and `M` ≤ 400.

### Input Format

The first line of input consists of two space-separated integers `N` and `M`.

The next `N` lines each consist of a single integer `R _{i}`, for

`i`= 1..

`N`.

The next

`N`lines each consist of a single integer

`P`, for

_{i}`i`= 1..

`N`.

The next

`M`lines each consist of two space-separated integers

`X`and

_{i}`Y`, for

_{i}`i`= 1..

`M`.

### Output Format

Output two integers – the minimum and maximum total scores that Bond could possibly get.

### Sample Input

3 5 10 100 1000 10 1 9 4 20 0 -10 1001 0 0 0 -300 -300

### Sample Output

21 30

### Explanation

Bond's total score is 21 if `P` = [1, 9, 10].

Bond's total score is 30 if `P` = [10, 9, 1].

All Submissions

Best Solutions

**Point Value:** 12 (partial)

**Time Limit:** 4.00s

**Memory Limit:** 64M

**Added:** Apr 08, 2016

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...