J - Crossing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

xy -平面上の点 S(x_{\mathrm{s}}, y_{\mathrm{s}}) と点 T(x_{\mathrm{t}}, y_{\mathrm{t}}) が与えられます。 また、4 つの整数からなる 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 つ選ぶ
  • 次に、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} と 1 つ以上の共有点を持つならば、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 または 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

曲線 C として x 軸上を点 S(-2, 0) から T(2, 0) へ移動する経路を選び、 1 以上 4 以下の相異なる 3 個の整数として 2, 3, 4 を選ぶ場合を考えます。 このとき、

  • 曲線 C は、直線 P_2 x + Q_2 y = R_2 （すなわち、直線 y = 10 ）と共有点を持たない。
  • 曲線 C は、直線 P_3 x + Q_3 y = R_3 （すなわち、直線 x = -1 ）との共有点 (-1, 0) を持つため、W_3 = 3 円払う。
  • 曲線 C は、直線 P_4 x + Q_4 y = R_4 （すなわち、直線 -x + y = 0 ）と共有点 (0, 0) を持つため、W_4 = 5 円払う。

よって、支払う合計金額は 8 円であり、これが考えられる最小値です。

入力例 2

2 2
0 0 0 0
1 2 3 4
2 4 6 8

出力例 2

0

点 S と点 T が同一の点であることや、 異なる複数の i について直線 P_i x + Q_i y = R_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

Problem Statement

You are given points S(x_{\mathrm{s}}, y_{\mathrm{s}}) and T(x_{\mathrm{t}}, y_{\mathrm{t}}) in the xy-plane. You are also given N four-tuples (P_i, Q_i, R_i, W_i)(1 \leq i \leq N).

Consider the following procedure.

  • First, choose an arbitrary (directed) curve C from point S(x_{\mathrm{s}}, y_{\mathrm{s}}) to T(x_{\mathrm{t}}, y_{\mathrm{t}})
  • Next, choose arbitrary K distinct integers A_1, A_2, \ldots, A_K between 1 and N.
  • Then, for each i = 1, 2, \ldots, K, do the following:
    • If the curve C has one or more common points with the line P_{A_i} x + Q_{A_i} y = R_{A_i}, you pay W_{A_i} yen (the currency in Japan).

Print the minimum possible amount of money you pay in total in the procedure above.

Constraints

  • 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.
  • For all i = 1, 2, \ldots, N, neither point S nor point T is on the line P_i x + Q_i y = R_i.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4 3
-2 0 2 0
2 1 2 7
0 1 10 10
1 0 -1 3
-1 1 0 5

Sample Output 1

8

Consider the case where you choose a path along the x-axis from point S(-2, 0) to T(2, 0) as the curve C, and integers 2, 3, 4 as the 3 distinct integers between 1 and 4. Then,

  • The curve C does not have a common point with the line P_2 x + Q_2 y = R_2 (i.e. the line y = 10).
  • The curve C has a common point (-1, 0) with the line P_3 x + Q_3 y = R_3 (i.e. the line x = -1), so you pay W_3 = 3 yen.
  • The curve C has a common point (0, 0) with the line P_4 x + Q_4 y = R_4 (i.e. the line -x + y = 0), so you pay W_4 = 5 yen.

Therefore, you pay 8 yen in total, which is the minimum possible amount.

Sample Input 2

2 2
0 0 0 0
1 2 3 4
2 4 6 8

Sample Output 2

0

Point S and point T may be the same point. Also, lines P_i x + Q_i y = R_i may be identical for multiple different i's.

Sample Input 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

Sample Output 3

694