Một trò chơi trí tuệ khác mà Đan đã làm là trò chơi chặn đường. Trò chơi diễn ra trên một mê cung được biểu diễn bằng lưới ô vuông kích thước $m \times n$, các hàng của lưới được đánh số từ $1$ đến $n$, các cột của lưới được đánh số từ $1$ đến $n$, ô nằm giao giữa hàng $i$ và cột $j$ được gọi là ô $(i, j)$. Mỗi ô có thể là ô cấm (ô không được phép đi vào) hoặc là ô tự do (ô có thể đi vào). Một tên cướp đang ở ô $(1, 1)$ và cần di chuyển đến ô $(m, n)$, mỗi bước tên cướp có thể di chuyển sang một trong bốn ô chung cạnh là ô tự do. Nhiệm vụ của người chơi là cần đặt cảnh sát vào một số ô tự do để chặn đường không cho tên cướp đi được đến ô $(m, n)$, tên cướp không thể di chuyển vào ô có cảnh sát. Biết rằng có một số ô tự do có thể đặt cảnh sát, ví dụ nếu ô $(i, j)$ là ô có thể đặt cảnh sát thì sẽ mất chi phí $c_{ij}$ $(1 \leq c_{ij} \leq 9)$.

Yêu cầu: Tính chi phí ít nhất để chặn được tên cướp không di chuyển được đến ô $(m, n)$.

Input

• Dòng đầu chứa hai số nguyên dương $m, n$ $(m \times n > 1)$
• Dòng thứ $i$ $(1 \leq i \leq m)$ trong dòng $m$ sau, mỗi dòng chứa một xâu độ dài $n$ , kí tự thứ $j$ $(1 \leq j \leq n)$ chỉ gồm các loại kí tự sau:
  • Kí tự # mô tả ô tả ô là ô cấm.
  • Kí tự 1 đến 9 mô tả ô là ô tự do và có thể đặt cảnh sát với chi phí tương ứng từ đến.
  • Kí tự . mô tả ô là ô tự do và không được phép đặt cảnh sát.

Chú ý rằng ô $(1, 1)$ và ô $(m, n)$ luôn là ô tự do không được đặt cảnh sát.

Output

• Gồm một dòng chứa một số nguyên là chi phí ít nhất để đặt cảnh sát nhằm chặn tên cướp không di chuyển được đến ô $(m, n)$, nếu không tồn tại ghi $-1$.

Scoring

• Subtask $1$ ($30\%$ số điểm): $m \leq 2; n \leq 1000$.
• Subtask $1$ ($30\%$ số điểm): $m \times n \leq 2 \times 10^{3}$.
• Subtask $1$ ($30\%$ số điểm): $m \times n \leq 2 \times 10^{5}$.

Example

2 4
.#.1
..2.

2

2 4
....
..1.

-1

Đan rất yêu thích số học và thường tự thử thách bản thân bằng những bài toán tự nghĩ ra. Một bài toán mà Đan nghĩ ra như sau: Cho số nguyên dương $n$ và $k$, cần tính tổng các chữ số của các số tự nhiên không vượt quá $n$ và chia hết cho $k$.

Input

• Gồm hai dòng, mỗi dòng chứa hai số nguyên dương $n,k (k \leq n)$ tương ứng với bộ cần tính.

Output

• In ra hai dòng, mỗi dòng chứa một số nguyên là tổng các chữ số của các số tự nhiên không vượt quá và chia hết cho tương ứng với bộ trong dữ liệu vào.

Scoring

• Subtask $1$ ($30\%$ số điểm): $n \leq 10^6$.
• Subtask $2$ ($30\%$ số điểm): $n = 10^{x}$ với $1 \leq x \leq 12$.
• Subtask $3$ ($40\%$ số điểm): $n \leq 10^{12}$.

Example

5 2
25 10

6
3

Đan mới tạo ra một trò chơi trên một vòng tròn số như sau: Ban đầu máy tính sẽ tạo ngẫu nhiên $n$ số nguyên $a_{0}, a_{1}, \ldots, a_{n - 1}$ và xếp lần lượt từng số lên vòng tròn theo chiều kim đồng hồ (xem ví dụ dưới đây cho vòng tròn 8 số).

Người chơi sẽ vào vai là một chú thỏ và thực hiện các hành động:

Ban đầu chú thỏ sẽ chọn một vị trí $s\ (0 \leq s < n)$ để xuất phát.

Sau đó, chú thỏ sẽ thực hiện $k$ lần nhảy $123$ bắt đầu từ $s$ theo chiều kim đồng hồ trên vòng tròn. Các vị trí tương ứng với bước nhảy $1, 3$ chú thỏ sẽ được cộng điểm là số tại vị trí đó, các vị trí tương ứng với bước nhảy $2$ chú thỏ bị trừ điểm là số tương ứng tại vị trí đó. Chú thỏ cần tìm cách nhảy để đạt được nhiều điểm nhất.

Ví dụ, trong hình trên, với $s = 1$ và $k = 2$, ba số được tô màu đỏ $(a_{1}, a_{3}, a_{4})$ tương ứng với lần nhảy $123$ thứ nhất, ba số được tô màu xanh $(a_{5}, a_{7}, a_{0})$ tương ứng lần nhảy thứ hai.

Tổng điểm chú thỏ nhận được là: $(a_{1} - a_{3} + a_{4}) + (a_{5} - a_{7} + a_{0})$.

Một cách hình thức: Nếu tạo dãy gồm $n$ số bắt đầu từ phần tử thứ $s$ theo chiều kim đồng hồ ta nhận được dãy $b_{0}, b_{1}, \ldots, b_{n - 1}$, trong đó $b_{0} = a_{s}, b_{1} = a_{(s + 1) \% n}, \ldots, b_{n - 1} = a_{(s + n - 1) \% n}$. Khi đó, cần tìm các chỉ số $0 \leq x_{1} < y_{1} < z_{1} < x_{2} < y_{2} < z_{2} < \ldots < x_{k} < y_{k} < z_{k} \leq n - 1$ để tổng: $(b_{x_{1}} - b_{y_{1}} + b_{z_{1}}) + (b_{x_{2}} - b_{y_{2}} + b_{z_{2}}) + \ldots + (b_{x_{k}} - b_{y_{k}} + b_{z_{k}})$ đạt giá trị lớn nhất.

Yêu cầu: Cho vòng tròn số và số nguyên dương $k$, tính điểm lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên dương $n, k$ $(3 \times k \leq n)$.
• Dòng thứ hai chứa $n$ số nguyên $a_{0}, a_{1}, \ldots, a_{n - 1}$ $(|a_{i}| \leq 10^{9}$ với $0 \leq i \leq n - 1)$.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị tổng điểm lớn nhất đạt được.

Scoring

• Subtask $1$ ($20\%$ số điểm): $n \leq 20, k = 1$.
• Subtask $2$ ($20\%$ số điểm): $n \leq 20$.
• Subtask $3$ ($20\%$ số điểm): $n \leq 2000, k = 1$.
• Subtask $4$ ($20\%$ số điểm): $n \leq 200$.
• Subtask $5$ ($20\%$ số điểm): $n \leq 2000$.

Example

8 2
1 1 0 -1 1 1 0 -1

6