A. 小修和小栋生♂成树

这不是一道提交答案题。

这不是一道交互题。

小修正在和小栋一起造生成树。

他们各有一张 个点， 条边的图。他们希望在图中找出一些边，使得只含有这些边的图是森林或者环套树森林。

由于小修和小栋是情侣，所以他们决定作出一样的选择，具体来说，对于第 条边，两个人要么同时选择，要么同时不选择。

对于第 条边有 的权值，小修和小栋希望最终选择出来的边的权值和尽量大。

这里环套树森林的定义指的是每个联通块都是树或者环套树。

第一行包含两个整数 和 ，表示图的点数和边数。

接下来一行两个整数 ，分别表示小修对最终图的要求和小栋的要求，当 为 的时候，表示希望最后得到的是森林，如果 为 则是环套树森林。

接下来 行，每行 个整数 ，其中 表示这条边在小修的图中连接的点， 表示在小栋的图中连接的点。

数据不保证没有重边和自环。

输出一行一个整数，表示最大的边权和。

样例输入

6 5
1 1
1 2 1 2 1
2 3 2 3 1
3 4 3 4 1
1 4 5 6 1
5 6 1 4 1

样例输出

4

对于所有数据，满足

以下限制如不做特殊说明均表示不超过。