E - Moving Stones on a Grid Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は、0 \leq x, y \leq 1000 を満たす整数格子点からなるグリッド上に N 個の石を置いています。はじめ、石が置かれている位置の集合は S です。

高橋君は次の 2 種類の操作を好きな順序で 0 回以上何回でも行うことができます。

  • 右移動：点 (x, y) にある石を 1 つ選び、点 (x + 1, y) に移動する。ただし、x + 1 \leq 1000 である必要がある。
  • ワープ：点 (x, y) にある石を 1 つ選び、点 (\lfloor a_1 x \rfloor, \lfloor a_2 y \rfloor) に移動する。ただし、移動先の点も 0 \leq x, y \leq 1000 を満たす必要がある。

ここで、a_1 = P_1 / Q_1、a_2 = P_2 / Q_2 であり、\lfloor \cdot \rfloor は床関数（小数点以下切り捨て）を表します。

ただし、移動先の点にすでに別の石がある場合、その操作は行えません。

目標となる位置の集合 T が与えられます。石はすべて区別しないものとし、操作を繰り返すことで石が置かれている位置の集合を S から T に完全に一致させることができるか判定してください。可能な場合は、必要な操作回数の最小値を出力してください。不可能な場合は -1 を出力してください。

制約

  • 1 \leq N \leq 9
  • 1 \leq P_1, P_2 \leq 10
  • 1 \leq Q_1, Q_2 \leq 10
  • 0 \leq X_i \leq 1000 (1 \leq i \leq N)
  • 0 \leq Y_i \leq 1000 (1 \leq i \leq N)
  • 0 \leq A_i \leq 1000 (1 \leq i \leq N)
  • 0 \leq B_i \leq 1000 (1 \leq i \leq N)
  • (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
  • (A_i, B_i) \neq (A_j, B_j) (i \neq j)
  • 入力はすべて整数

入力

N P_1 Q_1 P_2 Q_2
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、石の個数 N、およびワープ操作のパラメータ P_1, Q_1, P_2, Q_2 がスペース区切りで与えられる。
  • 続く N 行では、初期の位置集合 S が与えられる。1 + i 行目 (1 \leq i \leq N) には、i 番目の石の初期座標 (X_i, Y_i) がスペース区切りで与えられる。
  • 続く N 行では、目標の位置集合 T が与えられる。N + 1 + i 行目 (1 \leq i \leq N) には、目標の i 番目の点の座標 (A_i, B_i) がスペース区切りで与えられる。

出力

石が置かれている位置の集合を S から T に一致させることが可能な場合は、必要な操作回数の最小値を整数で出力せよ。不可能な場合は -1 を出力せよ。

入力例 1

1 1 1 1 1
0 0
5 0

出力例 1

5

入力例 2

1 1 1 1 1
0 0
0 1

出力例 2

-1

入力例 3

2 1 1 1 1
0 0
1 0
3 0
2 0

出力例 3

4

入力例 4

3 1 2 1 2
4 4
8 8
16 16
2 2
4 4
8 8

出力例 4

3

入力例 5

9 1 1 1 1
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
0 0
2 0
4 0
6 0
8 0
10 0
12 0
14 0
16 0

出力例 5

36

Score : 433 pts

Problem Statement

Takahashi has placed N stones on a grid consisting of integer lattice points satisfying 0 \leq x, y \leq 1000. Initially, the set of positions where the stones are placed is S.

Takahashi can perform the following 2 types of operations any number of times (possibly zero) in any order:

  • Right Move: Choose one stone at point (x, y) and move it to point (x + 1, y). However, this requires x + 1 \leq 1000.
  • Warp: Choose one stone at point (x, y) and move it to point (\lfloor a_1 x \rfloor, \lfloor a_2 y \rfloor). However, the destination point must also satisfy 0 \leq x, y \leq 1000.

Here, a_1 = P_1 / Q_1, a_2 = P_2 / Q_2, and \lfloor \cdot \rfloor denotes the floor function (rounding down to the nearest integer).

Note that if there is already another stone at the destination point, the operation cannot be performed.

You are given a target set of positions T. Assuming all stones are indistinguishable, determine whether it is possible to make the set of positions where the stones are placed completely match T from S by repeating the operations. If it is possible, print the minimum number of operations required. If it is impossible, print -1.

Constraints

  • 1 \leq N \leq 9
  • 1 \leq P_1, P_2 \leq 10
  • 1 \leq Q_1, Q_2 \leq 10
  • 0 \leq X_i \leq 1000 (1 \leq i \leq N)
  • 0 \leq Y_i \leq 1000 (1 \leq i \leq N)
  • 0 \leq A_i \leq 1000 (1 \leq i \leq N)
  • 0 \leq B_i \leq 1000 (1 \leq i \leq N)
  • (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
  • (A_i, B_i) \neq (A_j, B_j) (i \neq j)
  • All input values are integers.

Input

N P_1 Q_1 P_2 Q_2
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains the number of stones N and the parameters for the warp operation P_1, Q_1, P_2, Q_2, separated by spaces.
  • The following N lines describe the initial set of positions S. The (1 + i)-th line (1 \leq i \leq N) contains the initial coordinates (X_i, Y_i) of the i-th stone, separated by spaces.
  • The following N lines describe the target set of positions T. The (N + 1 + i)-th line (1 \leq i \leq N) contains the coordinates of the i-th target point (A_i, B_i), separated by spaces.

Output

If it is possible to make the set of stone positions match T from S, print the minimum number of operations required as an integer. If it is impossible, print -1.

Sample Input 1

1 1 1 1 1
0 0
5 0

Sample Output 1

5

Sample Input 2

1 1 1 1 1
0 0
0 1

Sample Output 2

-1

Sample Input 3

2 1 1 1 1
0 0
1 0
3 0
2 0

Sample Output 3

4

Sample Input 4

3 1 2 1 2
4 4
8 8
16 16
2 2
4 4
8 8

Sample Output 4

3

Sample Input 5

9 1 1 1 1
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
0 0
2 0
4 0
6 0
8 0
10 0
12 0
14 0
16 0

Sample Output 5

36