logo AlgoBeat OnlineJudge
登录 注册

#102960. [BZOJ 2960] 跨平面

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

题目描述

输入格式

第一行两个整数n和m,表示点与线段的数目。   接下来n行,每行两个整数x和y,表示第i个点的坐标,点从1到n编号。   接下来m行,每行四个整数p,q,V1和V2,表示存在一条从第p个点连向第q个点的线段,激活p->q这个方向的费用为V1,另一个方向费用为V2。   保证若两条线段相交,则交点是它们的公共端点。

输出格式

输出一行一个正整数,表示最小总激活费用。

样例

样例输入

4 5
0 0
1 0
0 1
1 1
1 2 0 0
1 3 0 3
2 3 1 0
2 4 2 0
4 3 0 0

样例输出

3

数据范围与提示

对于100%的数据,n≤3000,区域数不超过1000,点坐标绝对值不超过1W,每条边激活费用不超过100。