题目描述

在一个 $N$ 行 $M$ 列的矩形国土中，一侧是湖泊（第 $1$ 行），另一侧是沙漠（第 $N$ 行）。每个格子代表一座城市，有各自的海拔高度。

水利设施有两种：

• 蓄水厂：只能建在第 $1$ 行（毗邻湖泊）的城市，用于将湖水抽到该城市蓄水池。
• 输水站：建在某城市的前提是：存在海拔更高且有公共边的相邻城市已建有水利设施。

要求：第 $N$ 行（干旱区）的每座城市都必须建有水利设施。

问题：

• 如果要求能满足，输出最少需要建造几个蓄水厂。
• 如果不能满足，输出干旱区中无法建有水利设施的城市数量。

输入格式

第一行两个整数 $N$ 和 $M$，表示国土的行数和列数。

接下来 $N$ 行，每行 $M$ 个整数，表示每座城市的海拔高度。

输出格式

如果能满足要求，输出的第一行是整数 $1$ ，第二行是一个整数，代表最少建造几个蓄水厂；

如果不能满足要求，输出的第一行是整数 $0$ ，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。

2 5
9 1 5 4 3
8 7 6 1 2

1
1

3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2

1
3

提示

样例 1 说明

只需要在海拔为 $9$ 的那座城市（第 $1$ 行第 $1$ 列）建造蓄水厂，即可让输水站覆盖整个干旱区。

样例 2 说明

至少需要 $3$ 个蓄水厂才能覆盖干旱区所有城市。

数据规模与约定

对于全部的测试点，保证 $1 \leq N, M \leq 500$，城市海拔高度不超过 $10^6$。