美丽的世界

题目描述

小猫和粉兔到美丽的异世界探险，他们打开了宝箱，其中共有 m 件装备。他们决定瓜分这些装备，每件装备都恰好由一人穿戴。小猫和粉兔各有 n 个装备栏，每栏至多穿戴一件装备。同一件装备由小猫和粉兔持有，用法可能是不同的，所以第 i 件装备必须装在小猫的第 x_i栏中，并能够给小猫提供a_i战斗力；而必须装在粉兔的第 y_i 栏中，并能给粉兔提供 b_i战斗力。每人的战斗力都是所有装备提供的战斗力之和。合作战斗力为两人的战斗力之积。求所有符合上述条件的分配方案中，合作战斗力最小是多少。保证存在至少一种合法的分配方案。

输入输出格式

输入格式：

从文件 world.in 中读入数据。

输入第一行包含两个正整数 n, m, 分别表示每个人的装备栏数和总装备数。

接下来m行，每行四个整数 x_i , y_i , a_i , b_i

输出格式：

输出到文件 world.out 中。

输出一行一个整数，表示合作战斗力的最小值。

输入输出样例

输入样例#1：

2 2
1 1 1 2
2 2 2 1

输出样例#1：

补充说明

【样例 1 解释】

假设小猫持装备 1, 粉兔持装备 2, 合作战斗力为 1 × 1 = 1;

假设小猫持装备 2, 粉兔持装备 1, 合作战斗力为 2 × 2 = 4;

但若一人独占两件装备，合作战斗力为 0。

选择语言：

标签：
难度：省选/NOIS
时间限制：2S
空间限制：512MB