问题陈述
您已获得积分 S(x_{\mathrm{s}}, y_{\mathrm{s}}) 和 T(x_{\mathrm{t}}, y_{\mathrm{t}}) 在 xy- 平面。 还给你 N 四元组 (P_i, Q_i, R_i, W_i)(1 \leq i \leq N).
考虑以下过程。
- 首先,选择任意(有向)曲线 C 从点 S(x_{\mathrm{s}}, y_{\mathrm{s}}) to T(x_{\mathrm{t}}, y_{\mathrm{t}})
- 接下来,选择任意 K 不同 整数 A_1, A_2, \ldots, A_K 之间 1 和 N.
- 然后,对于每个 i = 1, 2, \ldots, K,执行以下操作:
- 如果曲线 C 与该线有一个或多个公共点 P_{A_i} x + Q_{A_i} y = R_{A_i},您支付 W_{A_i} 日元(日本货币)。
打印您在上述过程中总共支付的最低可能金额。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- -10^9 \leq x_{\mathrm{s}}, y_{\mathrm{s}}, x_{\mathrm{t}}, y_{\mathrm{t}} \leq 10^9
- -10^9 \leq P_i, Q_i, R_i \leq 10^9
- 1 \leq W_i \leq 10^9
- P_i \neq 0 or Q_i \neq 0.
- 对于所有人 i = 1, 2, \ldots, N,两者都没有 S 也不点 T 已上线 P_i x + Q_i y = R_i.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
x_{\mathrm{s}} y_{\mathrm{s}} x_{\mathrm{t}} y_{\mathrm{t}}
P_1 Q_1 R_1 W_1
P_2 Q_2 R_2 W_2
\vdots
P_N Q_N R_N W_N
输出
打印答案。
示例输入 1
4 3 -2 0 2 0 2 1 2 7 0 1 10 10 1 0 -1 3 -1 1 0 5
示例输出 1
8
考虑您选择沿 x- 轴距点 S(-2, 0) to T(2, 0) 作为曲线 C, 和整数 2, 3, 4 作为 3 之间的不同整数 1 和 4。 然后,
- 曲线 C 与线没有公共点 P_2 x + Q_2 y = R_2 (即行 y = 10).
- 曲线 C 有一个共同点 (-1, 0) 与行 P_3 x + Q_3 y = R_3 (即行 x = -1),所以你付钱 W_3 = 3 日元。
- 曲线 C 有一个共同点 (0, 0) 与行 P_4 x + Q_4 y = R_4 (即行 -x + y = 0),所以你付钱 W_4 = 5 日元。
因此,您支付 总计 8 日元,这是可能的最低金额。
示例输入 2
2 2 0 0 0 0 1 2 3 4 2 4 6 8
示例输出 2
0
点 S 和点 T 可能是同一点。 还有,线路 P_i x + Q_i y = R_i 对于多个不同的可能是相同的 i的。
示例输入 3
20 17 -6 -77 40 99 -14 74 -48 27 -51 43 5 89 -39 -29 80 75 -55 59 17 39 -37 -68 38 62 14 31 43 49 49 -7 -65 13 -40 -45 36 32 -54 -43 99 77 -94 57 -22 12 -85 67 -46 72 95 68 55 67 -56 51 -38 22 32 -19 65 46 76 66 -53 8 35 -78 -41 30 -51 -85 24 64 45 -53 82 12 39 19 -52 86 -11 -67 -33 100
示例输出 3
694