题号：NC19783
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
给定两张图，第一张图有n1个点，第二张图有n2个点。共有m条边，每条边在两张图中同时出现。第i条边在第一张图中连接ai和bi，在第二张图中连接ci和di。第i条边的权值为ei。
你需要选择一些边，使得两张图的仅包含这些边的生成子图中，每个连通块要么是树，要么是环套树。最大化你选择的边的权值和。
输入描述:
第一行三个整数n1,n2,m (1≤ n1,n2 ≤ 500, 1≤ m ≤ 1000)，接下来m行每行五个整数ai,bi,ci,di,ei (1 ≤ ai,bi≤ n1, 1≤ ci,di ≤ n2,1 ≤ ei ≤ 105)。
输出描述:
输出一行一个整数表示最大权值和。
示例1
输入
复制
5 5 10
5 5 4 2 28
5 5 4 2 64
3 1 5 2 80
1 2 4 2 84
2 1 4 2 52
1 2 2 2 72
2 4 1 3 26
4 5 4 4 51
5 1 4 2 22
5 1 4 1 55