Một đất nước có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\). Từ thành phố \(i\) đến thành phố \(j\) có một con đường với độ dài \(d_{ij}\). Một trùm khủng bố vừa vượt ngục và theo thông tin khoanh vùng thì trùm khủng bố đang ở thành phố \(1\). Với lực lượng mỏng, cảnh sát chỉ có thể phong tỏa được một con đường.

Gọi \(l_i, l_{i}'\) tương ứng là độ dài đường đi ngắn nhất từ thành phố \(1\) đến thành phố \(i\) (\(i = 2, 3, \dots, n\)) trước và sau khi cảnh sát phong tỏa một con đường. Cảnh sát muốn lựa chọn một con đường để phong tỏa sao cho số lượng thành phố thỏa mãn \(l_{i}' > l_i\) là nhiều nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Tiếp theo là \(n\) dòng, mỗi dòng chứa \(n\) số nguyên mô tả ma trận kề biểu diễn độ dài các con đường. Giá trị \(-1\) mô tả không có đường nối, \(0\) cho đường chéo, các số còn lại không vượt quá \(10^9\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là số lượng \(l_{i}' > l_i\) nhiều nhất tìm được.

Example

3
0 1 5
1 0 2
1 2 0

2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 50\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 500\).

Nguồn: 3D'21