For the performance, the gymnasts use ribbons, which are placed on the table after the performance. The father of the best gymnast Anna K., in anticipation of the award, decided to write down the coordinates of the beginning and end of the ribbons. If the tape hung from the left edge of the table, then he set the left coordinate equal to zero, if the tape hung from the right end of the table, then he set the right coordinate equal to zero. If the tape hung from both sides, then he recorded both coordinates equal to zero. Do you have a file with this information. Determine how many points of the table turned out to be the largest thickness of the coating and what it is equal to. The table has a length Lmm. At the end of the performance of all the gymnasts, there was N tapes. Some ribbons have only one end hanging off the table, some have both. All tapes lie horizontally. The ribbons stack on top of each other.
Input
The first line of the file contains two numbers - L, N (1 <= L <= 10000, 1 <= N <= 10000). The following N lines contain 2 numbers each - l, r (1 <= l <= r <= L) - left and right ends of the tapes relative to the left edge of the table.
In your answer, indicate two numbers separated by a space - the maximum thickness of the tape table cover and the number of points with such a thickness.
Запрещенные операторы:sort