Никир устроился работать регулировщиком очередей в компанию «Чёрный Контур». Ему нужно будет выбирать порядок обслуживания клиентов. Всего есть \(n\) очередей, в каждой из которых изначально стоит \(0\) человек. В каждый из следующих \(n\) моментов времени происходит два последовательных события:
- Во все очереди приходят новые клиенты. Более формально, в \(j\)-й момент времени количество людей в \(i\)-й очереди увеличивается на положительное целое число \(a_{i,j}\).
- Никир выбирает ровно одну из \(n\) очередей, которую будут обслуживать в этот момент времени. Количество клиентов в этой очереди становится равным \(0\).
Пусть количество людей в \(i\)-й очереди после всех событий равно \(x_i\). Никир хочет, чтобы MEX\(^{\dagger}\) набора чисел \(x_1, x_2, \ldots, x_n\) был как можно больше. Помогите ему определить максимальное значение, которое он сможет получить при оптимальном порядке обслуживания очередей.
\(^{\dagger}\)Наименьшее исключенное (MEX) набора чисел \(c_1, c_2, \ldots, c_k\) определяется как наименьшее неотрицательное целое число \(y\), которое не встречается в наборе чисел \(c\).
Например:
- \(\operatorname{MEX}([2,2,1])= 0\), так как \(0\) не принадлежит массиву.
- \(\operatorname{MEX}([3,1,0,1]) = 2\), так как \(0\) и \(1\) принадлежат массиву, а \(2\) нет.
- \(\operatorname{MEX}([0,3,1,2]) = 4\), так как \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, а \(4\) нет.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — максимальное значение \(\operatorname{MEX}([x_1, x_2, \ldots, x_n])\), которое можно получить.
Примечание
В первом наборе входных данных можно обслужить вторую очередь в момент времени \(1\) и первую очередь в момент времени \(2\). В первой очереди останется \(x_1 = 0\) человек, во второй очереди останется \(x_2 = 1\) человек. Тогда ответ равен \(\operatorname{MEX}([0, 1]) = 2\).
Во втором наборе входных данных можно оба раза обслужить первую очередь. В первой очереди останется \(x_1 = 0\) человек, во второй очереди останется \(x_2 = 20\) человек. Тогда ответ равен \(\operatorname{MEX}([0, 20]) = 1\).
В третьем наборе входных данных можно обслужить третью очередь в момент времени \(1\), вторую очередь в момент времени \(2\) и первую очередь в момент времени \(3\). В первой очереди останется \(x_1 = 0\) человек, во второй очереди останется \(x_2 = 1\) человек, в третьей очереди останется \(x_3 = 2\) человека. Тогда ответ равен \(\operatorname{MEX}([0, 1, 2]) = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2
2 1
2
10 10
10 10
3
2 3 3
4 4 1
2 1 1
4
4 2 2 17
1 9 3 1
5 5 5 11
1 2 1 1
|
2
1
3
3
|