QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[0]

# 8760. 不等式

Statistics

题目描述

给定 n,m,以及 m 个形如 axiayi+azi(1im) 的条件。问是否有一组正整数 (a1,a2,,an) 满足所有条件,并且 a1+a2++an109。如果有,输出 a1+a2++an 的最小值;如果无解,输出 1

输入格式

从标准输入读入数据。

第一行两个整数 n,m(1n,m2×105)

之后 m 行,第 i 行三个整数 xi,yi,zi,表示一个限制 axiayi+azi(1xi,yi,zin)

输出格式

输出到标准输出。

输出一行一个整数,表示答案。

样例

输入

5 2
1 2 3
3 4 5

输出

8

解释

和最小的解为 (3,1,2,1,1),和为 8