Problem 1155. -- 张老师的训练II

1155: 张老师的训练II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 33  Solved: 6
[Submit][Status][Web Board]

Description

    程序设计竞赛即将开始,张老师正在绞尽脑汁为学弟学妹们准备训练题,组出一套训练赛
    张老师选出了n种类型的题目,为了考察同学们对知识的掌握程度,张老师决定所出的题目中,每一类型的题目至少包含一道。
    对于每一种类型的题目,张老师努力找到了k道题,其中每一道题对应着一个独立的难度系数。
    需要注意的是,在所有类型的题目中,没有任何两道题目拥有相同的难度系数。
    现在,张老师想让所出题目的难度跨度尽可能的小,也就是让出的所有题目中最小难度的和最大难度尽量接近,
    他想请聪明的你帮忙求出最小的难度区间的长度!

Input

 第一行两个整数n, k(1 <= n <= 105, 1 <= k <= 105, 保证n*k <= 105),分别表示题目的种类数和每种题目的数量。
 接下来n行,每行k个整数,第i+1行的第j个数表示第i种题目的第j道题的难度系数p(i,j), (1 <= p(i,j) <= 109)

Output

输出一行,表示张老师能选择的最小难度区间的长度

Sample Input

 3 3
 4 2 1
 3 5 7
 6 8 9

Sample Output

2

HINT

Source

[Submit][Status]