В один из дней школьник Марк плохо себя вел, поэтому преподаватель Саша вызвал его к доске.
Саша дал Марку таблицу из \(n\) строк и \(m\) столбцов. Его задача — расставить в таблице числа \(0, 1, \ldots, n \cdot m - 1\) (каждое нужно использовать ровно один раз) так, чтобы максимизировать сумму MEX\(^{\text{∗}}\) по всем строкам и столбцам. Более формально, нужно максимизировать \(\)\sum\limits_{i = 1}^{n} \operatorname{mex}(\{a_{i,1}, a_{i,2}, \ldots, a_{i,m}\}) + \sum\limits_{j = 1}^{m} \operatorname{mex}(\{a_{1,j}, a_{2,j}, \ldots, a_{n,j}\}),\(\) где \(a_{i,j}\) — число в \(i\)-й строке и \(j\)-м столбце.
Сашу не интересует, как Марк расставил числа, поэтому он просит его сказать лишь одно число — максимальную сумму MEX по всем строкам и столбцам, которую можно получить.
Выходные данные
Для каждого набора входных данных выведите максимальную возможную сумму \(\operatorname{mex}\) по всем строкам и столбцам.
Примечание
В первом наборе входных данных единственный элемент равен \(0\), сумма \(\operatorname{mex}\) множества чисел первой строки и \(\operatorname{mex}\) множества чисел первого столбца это \(\operatorname{mex}(\{0\}) + \operatorname{mex}(\{0\}) = 1 + 1 = 2\).
Во втором наборе входных данных оптимальная таблица может выглядеть следующим образом:
Тогда \(\sum\limits_{i = 1}^{n} \operatorname{mex}(\{a_{i,1}, a_{i,2}, \ldots, a_{i,m}\}) + \sum\limits_{j = 1}^{m} \operatorname{mex}(\{a_{1,j}, a_{2,j}, \ldots, a_{n,j}\}) = \operatorname{mex}(\{3, 0\}) + \operatorname{mex}(\{2, 1\})\) \(+ \operatorname{mex}(\{3, 2\}) + \operatorname{mex}(\{0, 1\}) = 1 + 0 + 0 + 2 = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
2 2
3 5
|
2
3
6
|