An buộc phải ngồi đọc cho xong quyển sách mà sư phụ cho mượn mấy hôm trước. Đọc được một lúc, An cảm thấy buồn chán và nghĩ cách làm sao cho đỡ buồn.

Chợt An nghĩ ra một cách: An bắt đầu đếm số chữ số dùng để đánh số trang trong toàn bộ quyển sách. Cuối cùng, An đếm được ~N~ chữ số.

An còn phát hiện ra một điều đặc biệt là ở ba trang đầu tiên của quyển sách không hề có ghi số trang gì cả mà chỉ có ghi ở trang thứ tư trở đi (trang ~4~ được ghi số ~4~, trang ~5~ được ghi số ~5~, trang ~6~ được ghi số ~6~, vân vân ~\ldots~).

Sau khi trả lại quyển sách cho sư phụ, An không nhớ quyển sách có bao nhiêu trang mà chỉ còn nhớ được số ~N~.

Yêu cầu: Cho trước số ~N~, hãy lập trình giúp An tìm ra số trang của quyển sách đó.

Input

Gồm một số nguyên ~N~ ~(1 \leq N \leq 10000)~ cho biết số chữ số dùng để đánh số trang cho quyển sách.

Output

In ra một số nguyên ~P~ cho biết tổng số trang của quyển sách.

Sample Input 1

1

Sample Output 1

4

Sample Input 2

2

Sample Output 2

5

Sample Input 3

3

Sample Output 3

6

Sample Input 4

10

Sample Output 4

11

Notes

Luôn đảm bảo An đã đếm đúng số chữ số, tức là luôn tồn tại lời giải.

Phép toán ~\text{mod}~ được áp dụng trên số nguyên và cho kết quả là số dư của phép chia số nguyên. Ví dụ: ~24 \text{ mod } 16~ cho kết quả ~8~, còn ~15 \text{ mod } 16~ cho kết quả ~15~.

Cho trước bốn số nguyên dương ~N~, ~P~, ~A~, ~B~. Lặp lại thao tác sau đây nhiều lần: lấy số ~N~ và thay thế nó bằng một trong ba số nguyên ~(N + A) \text{ mod } P~, ~(N + B) \text{ mod } P~ hoặc ~(N + A + B) \text{ mod } P~. Hãy cho biết cần thực hiện ít nhất bao nhiêu thao tác thay thế ở trên để từ số ~N~ ta được số ~R~.

Input

Dòng đầu tiên ghi hai số ~N~, ~P~ (~0 < N \leq 10^9~, ~0 < P \leq 10^6~).

Dòng thứ hai ghi ba số ~A~, ~B~, ~R~ (~0 < A, B \leq P~, ~0 \leq R < P~, ~N \neq R~).

Output

Ghi một số nguyên cho biết số thao tác ít nhất, nếu không thể thực hiện được thì ghi ~-1~.

Sample Input 1

20 16
3 4 15

Sample Output 1

2

Sample Input 2

6 8
2 4 1

Sample Output 2

-1

Notes

Ở test đầu tiên, với ~N = 20~, thực hiện thay thế ~N~ như sau:

• Lần 1: thay ~N = 8~ vì ~(20 + 4) \text{ mod } 16 = 8~

• Lần 2: thay ~N = 15~ vì ~(8 + 3 + 4) \text{ mod } 16 = 15~

Sau 2 lần thay thế, kết quả được ~N = R = 15~.

Bạn An đang đứng ở vị trí có tọa độ ~(1,1)~ trên bản đồ và muốn đi đến thành phố ByteCity ở tọa độ ~(N,N)~.

Đây là bản đồ hình vuông, bản đồ có chứa các độ cao ~A[i][j]~ tại mỗi tọa độ ~(i,j)~. Bạn An chỉ đi được từ một ô sang các ô kề cạnh.

Yêu cầu: Bạn An không giỏi leo lên (hoặc xuống) đồi nên muốn nhờ bạn lập trình tìm con đường sao cho độ lệch lớn nhất của độ cao hai ô kề cạnh là nhỏ nhất có thể được. Độ lệch của độ cao hai ô được hiểu là trị tuyệt đối của hiệu độ cao của hai ô này.

Input

Dòng đầu tiên ghi hai số nguyên dương ~N~ ~(1 < N \le 500)~

~N~ dòng tiếp theo, mỗi dòng ghi ~N~ số nguyên dương ~A[i][j]~ cho biết độ cao của các vị trí tương ứng tại dòng i và cột j trên bản đồ ~(0 \le A[i][j] \le 10^6)~

Output

Một số nguyên dương duy nhất cho biết độ lệch lớn nhất của độ cao hai ô kề cạnh trên con đường tìm được.

Sample Input 1

4
3 5 7 7
2 4 4 7
3 3 5 4
9 5 8 5

Sample Output 1

1