Under construction

Still being built. Things may change

Swallow Messenger

Interview

Time limit2sMemory limit1024 MB

Summary
Given N points and M allowed integer slopes, count the ordered pairs of distinct points that lie on a common line with one of those slopes.
Level

Medium4 of 10

Topics
Hash map, Math
Solved
No attempts yet

Problem

Hanyang wants to tie a letter to one of his MM swallows and send it to Sejong.

However, the swallows Hanyang raises are stubborn. Each one flies only along a straight path from Hanyang's position, following its own fixed slope.

Sejong must stand on this straight path to receive Hanyang's letter, which makes swallow communication possible.

You are given NN coordinates where Hanyang and Sejong can be placed.

Count every way to place the two of them so that swallow communication is possible.

Input

The first line contains NN and MM, separated by a space. (2≤N≤500002 \le N \le 50000, 1≤M≤101 \le M \le 10)

The second line contains MM slopes K1,K2,…,KMK_1, K_2, \dots, K_M, separated by spaces. All KK values are distinct. (−10≤Ki≤10-10 \le K_i \le 10)

The next NN lines each contain the xx and yy coordinates of point ii, separated by a space. All coordinates are distinct. (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9)

All input values are integers.

Output

Print the number of ways to place Hanyang and Sejong so that swallow communication is possible.

Hanyang and Sejong cannot be placed on the same coordinate.

Hint

In mathematics, slope is a number that describes how steeply a line is tilted. In the Cartesian coordinate system, the slope of a line can be written as follows.

slope=change in ychange in x\text{slope} = \frac{\text{change in } y}{\text{change in } x}

Examples1

  1. Example 1

    Input
    5 2
    1 -1
    1 1
    2 2
    3 2
    3 3
    5 -1
    
    Expected output
    8