← 返回题目列表

AtCoder · past202212_j

J. 穿越

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

问题陈述

您已获得积分 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