#2488. 「2018 集训队互测 Day 4」小修和小栋生♂成树

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

不是一道提交答案题。

不是一道交互题。

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

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

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

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

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

输入格式

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

接下来一行两个整数 \text{type}_1,\text{type}_2 ,分别表示小修对最终图的要求和小栋的要求,当 \text{type} 1 的时候,表示希望最后得到的是森林,如果 \text{type} 2 则是环套树森林。

接下来 m 行,每行 5 个整数 u1_i,v1_i,u2_i,v2_i,a_i ,其中 u1_i,v1_i 表示这条边在小修的图中连接的点, u2_i,v2_i 表示在小栋的图中连接的点。

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

输出格式

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

样例

样例输入

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

数据范围与提示

对于所有数据,满足 1\le n,m\le 300,1\le a_i\le 10^5

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

子任务编号 n m 特殊限制 分数
1 300 300 u1_i=u2_i,v1_i=v2_i 3
2 20
3 7 300 \text{type}_1=\text{type}_2=1 7
4 5 11
5 300 \text{type}_1=\text{type}_2=1 15
6 \text{type}_1=\text{type}_2=2 17
7 70 10
8 300 34