Trong kho hàng nông sản của An, cam tươi được xếp trên khay lưới kích thước \(N \times M\). Các ô chứa cam được ký hiệu:

• 0: Ô trống không chứa cam.
• 1: Cam tươi nguyên vẹn.
• 2: Cam thối hỏng.

Do không khí ẩm, bào tử nấm từ cam thối sẽ phát tán và lây lan sang các ô chứa cam tươi kề cạnh (4 hướng: trên, dưới, trái, phải). Cứ sau mỗi phút, cam tươi kề cạnh cam thối sẽ biến thành cam thối.

Hãy giúp An tính số phút tối thiểu để toàn bộ cam tươi trong khay bị lây thối hết. Nếu có một số quả cam tươi bị cô lập và không bao giờ bị thối, hãy in ra -1.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N, M \le 500\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên mô tả khay chứa cam.

Định dạng đầu ra

• Một số nguyên duy nhất biểu thị số phút tối thiểu hoặc -1.

Ví dụ

Input:

3 3
2 1 1
1 1 0
0 1 1

Output:

4