S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1~N。他们之间的关系自然也极 不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨 气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之 间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并 造成影响力为 c 的冲突事件。 每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表， 然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力， 如果影响很坏，他就会考虑撤换警察局长。 在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在 两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只 要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那 么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力小？这个小值是多少？

对于 30%的数据有 N≤15。

对于 70%的数据有 N≤2000，M≤50000。

对于 100%的数据有 N≤20000，M≤100000。

输出文件 prison.out 共 1 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱 中未发生任何冲突事件，请输出 0。

NOIP2010提高组