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