bobo המסכן לכוד במבוך!

המבוך מחולק ל־$n$ שורות ול־$m$ עמודות. בכל תא במבוך יש קיר לאורך אחד האלכסונים. לכן יש רק שני סוגי תאים.

בזכות כוח הקסם שלו, bobo יכול לשנות את סוג התא $(i, j)$ בעלות $c_{i,j}$. בתור קוסם טוב לב, bobo רוצה שהמבוך לא יוכל עוד ללכוד אנשים. כלומר, לא יישאר שום אזור סגור המוקף בקירות.

מצאו את העלות הכוללת המינימלית שבה bobo יכול להשיג את מטרתו.

קלט

השורה הראשונה מכילה 2 מספרים שלמים $n, m$ ($1 \le n, m \le 1000$).

כל אחת מ־$n$ השורות הבאות מכילה $m$ תווים, המציינים את כיוון הקיר בתא.

כל אחת מ־$n$ השורות האחרונות מכילה $m$ מספרים שלמים $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

פלט

מספר יחיד המציין את העלות המינימלית.

דוגמאות

קלט 1

3 3
/\/
\/\
/\/
1 3 3
3 1 3
3 3 3

פלט 1

2

קלט 2

2 2
\/
/\
1000 1000
1000 1000

פלט 2

0