如果两个所选的三角形有重合部分的话，那么这种情况肯定是不会出现的。因为如果把这两个三角形合成一个大三角形的话，不仅覆盖面积会增大，而且花费的代价还不会多。

于是我们可以想到用 dp 来解决，设 $dp_i$ 表示删完横坐标为 0 到 $i$ 中的点的最小代价，很容易得到状态转移方程：$dp_i = \min(dp_j + (i-j-1) \times A + cost)$。这里的 $cost$ 指的是所有满足 $j < x \leq i, 1 \leq y < k-i$ 的条件的点，因为只有这些点没有被当前所选的这个三角形所包含，所以需要加上这些点的代价。但是这个方程转移的时间复杂度是 $O(n^2)$ 的，所以还需要优化。

我们可以发现一些性质，从 $i$ 变到 $i+1$ 的过程中，我们对于所有转移代价都需要$+A$,而在 $cost$中，我们发现仅仅只是加上了$i+1$行的情况，而对于这行上的点纵坐标为 $x_i$ 他会给没覆盖到他的三角形加一个代价，所以对于 $j>x_i$ 的 $cost$ 会增加 $c_i$,这里使用线段树区间加即可。

所以每次更新我们都可以只修改之前所有 $A$ 和 $cost$ 的值就行了，而这两个操作都可以用线段树来维护，时间复杂度 $O(n\log n)$。注意线段树维护的每一个 $j$ 的值已经是 $dp_j + (i-j-1) \times A + cost$ 了，所以直接查询最小值就可以了。

注意因为坐标轴的最小值为 0，所以我们还需要维护一个下标为 $-1$ 的值，这个值代表前面还什么都没有选时的代价。

综上，我们需要支持一个区间加，单点修改+区间查询 $min$ 的线段树，初始可以把线段树赋值成无穷大。