AT_past202212_j 横断

给定平面上的两个点 $S(x_{\mathrm{s}}, y_{\mathrm{s}})$ 和 $T(x_{\mathrm{t}}, y_{\mathrm{t}})$，以及 $N$ 个四元组 $(P_i, Q_i, R_i, W_i)$（$1 \leq i \leq N$）。 请考虑如下的过程： - 首先，在平面上从点 $S(x_{\mathrm{s}}, y_{\mathrm{s}})$ 到点 $T(x_{\mathrm{t}}, y_{\mathrm{t}})$ 上任选一条（有向）曲线 $C$。 - 接着，在 $1$ 到 $N$ 之间任选 $K$ 个**不同的**整数 $A_1, A_2, \ldots, A_K$。 - 对于每个 $i = 1, 2, \ldots, K$，执行以下操作： - 如果曲线 $C$ 与直线 $P_{A_i}x + Q_{A_i}y = R_{A_i}$ 至少有一个公共点，你需要支付 $W_{A_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 考虑选择沿 $x$ 轴从点 $S(-2, 0)$ 到 $T(2, 0)$ 的路径 $C$，并选择 $1$ 到 $4$ 中的整数 $2, 3, 4$ 作为这 $3$ 个不同的整数。那么： - 曲线 $C$ 与直线 $P_2x + Q_2y = R_2$（即 $y = 10$）没有公共点。 - 曲线 $C$ 与直线 $P_3x + Q_3y = R_3$（即 $x = -1$）有公共点 $(-1, 0)$，因此你需要支付 $W_3 = 3$ 日元。 - 曲线 $C$ 与直线 $P_4x + Q_4y = R_4$（即 $-x + y = 0$）有公共点 $(0, 0)$，因此你需要支付 $W_4 = 5$ 日元。 因此，你总共需要支付 $8$ 日元，这也是可能的最小花费。 ### 样例解释 2 点 $S$ 和点 $T$ 可能是同一个点。同样，$P_ix + Q_iy = R_i$ 也可能对不同的 $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$ 或 $Q_i \neq 0$ - 对所有 $i = 1, 2, \ldots, N$，点 $S$ 和点 $T$ 都不在直线 $P_ix + Q_iy = R_i$ 上。 - 所有输入均为整数。 由 ChatGPT 5 翻译