← 返回题目列表

AtCoder · maximum_cup_2023_g

G. 针对野猪的措施

中文机器翻译题面 查看原题

配点 : 100 点

問題文

S先生 xy 在飞机上 我决定开始在 (X,Y) 的田地里务农。

然而,在飞机上 N 有一种野猪头的动物正试图破坏田地。 第i 头野猪是 我住在 (x_i,y_i) 。

当S先生向政府部门寻求解决办法时, 提出了M 计划。
i 第一个平面图是一条直线 y = a_i x + b_i 如果您想在上方安装围栏 2^{i-1} 花费日元。

如何保护您的田地 i=1,2,\ldots,N 对于一切, 连接(X,Y) 和 将其放在 (x_i,y_i) 的线段(包括端点)与某个栅栏对应的直线必须有交点。

计划 0 选择或更多并执行以计算保护该字段所需的最低金额。 C 比如说日元。C 请计算 (10^9+7) 求余数。 打印除以
但是,如果无论你选择什么计划都无法保护你的领域,那么 请输出 -1 。 最好选择并执行

制約

  • 1 \leq N,M \leq 2 \times 10^5
  • -10^9 \leq X,Y,x_i,y_i,a_i,b_i \leq 10^9
  • (X,Y) \neq (x_i,y_i)
  • 输入全部为整数

入力

输入将以以下形式通过标准输入给出。

N M X Y
x_1 y_1
\vdots
x_N y_N
a_1 b_1
\vdots
a_M b_M

出力

输出答案。


入力例 1

3 3 1 1
2 4
3 9
-5 10
-4 8
3 -3
-7 7

出力例 1

5

1,3 计划,C= 2^{1-1} + 2^{3-1} = 5 ,因此,5 请计算 (10^9+7) 所得的余数 请输出 5 是预期输出。


入力例 2

2 2 0 0
10 3
10 3
5 2
5 2

出力例 2

-1

同一坐标或同一规划中可能存在多头公猪(所需数量除外)。