线路改建后的余额

难度：T2

【知识点：综合算法与限时决策】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

保留所有已建免费线路，可以再购买候选线路使全部顶点连通。在预算 $B$ 内采用新增费用最低的方案，求剩余预算；区分无法连通与可以连通但超预算两种情况。

输入格式

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$；$m$ 为随后给出的带权边条数。每条带权边独占一行，依次为 $u,v,w$，表示从 $u$ 到 $v$ 的边及权值 $w$；无向边可双向通行，有向边只能从 $u$ 到 $v$ 通行。 已建免费线路先输入，共 $k$ 行，每行只有两个端点 $u,v$。

输入$n$、$k$、$m$、$B$；$k$条已建免费无向边，再输入$m$条候选无向边$u$、$v$、$w$。已建边永久保留。

输出格式

不能连通输出IMPOSSIBLE；最小新增费用超过$B$输出OVER_BUDGET；否则输出剩余预算。

数据范围

$1\le n\le 100000$，$0\le k,m\le 200000$，$0\le B\le 10^14$，$0\le w\le 10^9$，编号在$1$..$n$。

样例输入

1 0 0 0

样例输出

0