Tháp cát (Bản 1)

Từ xa xưa, tại vùng đất Sa Ngọc, người dân tôn thờ những ngọn tháp được xây dựng từ cát linh thiêng. Mỗi ngọn tháp là một bảng đá đứng gồm \(n\) tầng và \(m\) cột, trong đó có những ô chứa khối cát thiêng và những ô trống.

Theo truyền thuyết, để khơi dậy nguồn năng lượng từ các tháp, người thực hiện nghi lễ phải làm rơi các khối cát xuống các bàn thờ ở chân cột. Mỗi cột có một bàn thờ riêng, và để hoàn thành nghi lễ, số lượng khối cát rơi xuống mỗi bàn thờ phải đạt ít nhất \(a_i\) khối.

Tuy nhiên, việc làm rơi cát không đơn giản. Khi một khối cát ở ô \((i, j)\) bị đánh thức, nó rơi xuống, đi qua toàn bộ các ô bên dưới trong cùng cột. Trên đường đi, nếu có khối cát nào nằm kề bên theo 4 hướng (trái, phải, trên, dưới), chúng cũng sẽ bị đánh thức và bắt đầu rơi, tạo thành một chuỗi phản ứng dây chuyền.

Trong mỗi lượt hành lễ, bạn chỉ có thể đánh thức một khối cát bất kỳ.

Bạn được giao nhiệm vụ tìm số lượt hành lễ tối thiểu để hoàn tất nghi lễ, tức là để mỗi cột thu đủ số lượng khối cát quy định.

Input

Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) \((1 \le n \cdot m \le 400,000)\) --- số hàng và số cột của bảng tháp cát.

Mỗi dòng trong \(n\) dòng tiếp theo chứa đúng \(m\) ký tự, mô tả trạng thái của bảng. Ký tự "." biểu thị một ô trống, còn ký tự "#" biểu thị một ô chứa cát.

Dòng cuối cùng chứa \(m\) số nguyên không âm \(a_1, a_2, \ldots, a_m\) \((0 \le a_i \le n)\) --- số lượng cát tối thiểu cần phải rơi xuống bàn thờ ở mỗi cột tương ứng.

Lưu ý ở bản này: Đảm bảo rằng \(a_i\) đúng bằng số lượng cát có sẵn trong cột \(i\).

Output

In ra một số nguyên duy nhất --- số lượt đánh thức tối thiểu cần thực hiện để hoàn thành nghi lễ cho toàn bộ tháp.

Example

5 7
#....#.
.#.#...
#....#.
#....##
#.#....
4 1 1 1 0 3 1

3