لقد علق bobo المسكين في متاهة!

تنقسم المتاهة إلى $n$ صفوف و$m$ أعمدة. تحتوي كل خلية في المتاهة على جدار يمتد على طول أحد القطرين. ولذلك لا يوجد سوى نوعين من الخلايا.

بفضل قوة bobo السحرية، يمكنه تغيير نوع الخلية $(i, j)$ بتكلفة $c_{i,j}$. وبصفته ساحرًا طيبًا، يريد bobo أن يجعل المتاهة عاجزة عن حبس الناس بعد الآن. أي إنه يجب ألا تبقى أي منطقة مغلقة تحيط بها الجدران.

أوجد أقل تكلفة إجمالية يحتاج إليها bobo لتحقيق هدفه.

الإدخال

يحتوي السطر الأول على عددين صحيحين $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