配点 : 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
同一坐标或同一规划中可能存在多头公猪(所需数量除外)。