Under construction

Still being built. Things may change

Shooting Practice

Interview

Time limit1sMemory limit1024 MB

Summary
Starting from the cursor at (0, 0), repeatedly shoot the farthest target and sum the squared distances from the cursor to each shot target over M moves.
Level

Easy2 of 10

Topics
Simulation, Brute force
Solved
No attempts yet

Problem

Jeongwoo, who wants to improve his FPS game skills, is practicing target shooting. In this drill, the computer screen is treated as a two-dimensional coordinate plane, so the position of each target can be written as coordinates. Moving right increases the xx value, and moving up increases the yy value.

At the start, the mouse cursor is always at (0,0)(0, 0), and NN targets are on the screen. When the cursor moves to a target and clicks it, that target disappears and Jeongwoo earns points. The points earned equal the squared distance from the cursor's position before the move to that target. The distance is the Euclidean distance, which is the straight-line distance between two points.

Whenever a target is removed, a new target appears on the screen. Jeongwoo uses a strategy where each move hits the target that is farthest from the current cursor position. Find the total score Jeongwoo earns after repeating this process MM times. No two targets appear at the same position, and before each move the farthest target from the cursor is always unique.

Input

The first line contains two integers NN and MM, separated by a space. (1≤N,M≤100)(1 \le N, M \le 100)

From the second line onward, the next NN lines each contain two integers xix_i and yiy_i, separated by a space, giving the coordinates of the targets currently on the screen. (−100≤xi,yi≤100)(-100 \le x_i, y_i \le 100)

The next MM lines each contain two integers xjx_j and yjy_j in order, giving the coordinates of the targets that appear next. (−100≤xj,yj≤100)(-100 \le x_j, y_j \le 100)

Output

Print the total score Jeongwoo earns.

Examples1

  1. Example 1

    Input
    2 3
    -1 0
    5 0
    1 2
    1 1
    6 2
    
    Expected output
    69