一般に、直線は \(xy\) -平面を \(2\) つの領域に分断しますが、 与えられた \(N\) 個の直線のうち、点 \(S\) と点 \(T\) を異なる領域に分ける直線については、曲線 \(C\) はこれを遮る必要があります。 反対に、それ以外の直線については、曲線 \(C\) として \(S\) と \(T\) を結ぶ線分を選ぶことで遮らずに済みます。

よって、

• まず、与えられた各直線についてそれが 通らなければならない直線 である（つまり、\(S\) と \(T\) を異なる領域に分けるか）を判定し、
• 選ぶ \(K\) 個の直線として、まず 通らなくても良い直線 を優先的に、次に、通らなければならない直線 を費用が小さいものから優先的に選べば良いです。
• このとき、選んだ \(K\) 個の直線に含まれる、 通らなければならない直線 の費用の和が本問題の答えとなります。

直線が \(S\) と \(T\) を異なる領域に分けるかを判定する方法について、 一般にある点 \((p, q)\)が 直線 \(ax + by = c\) で分けられた \(xy\) -平面の \(2\) つの領域のどちらにあるかを判定するには、\(ap+bq < c\) と \(ap+bq>c\) のどちらが成り立つのかを判定すれば良いです。