Problem2925--狼抓羊

2925: 狼抓羊

Time Limit: 2 Sec  Memory Limit: 162 MB
Submit: 161  Solved: 43
[Submit] [Status] [Web Board] [Creator:]

Description


有一个这样的图, 先读横向边, 再读纵向, 再是斜边, 这是一个m * n的方格, 兔子们都呆在左上角的起点(1, 1), 兔子们都要去右下角(m, n);
现在有一个狼老大, 每一只狼只能抓一只兔子, 所以他想要用尽量少的狼抓完所有的兔子;
每条道路是双向的, 道路的权值表示该道路最多出现多少只兔子, 狼就要在道路上拦截兔子们

Input

读入m, n (m, n <= 1000)
m行, n - 1个数表示横向道路
m - 1行, n个数表示纵向道路
m - 1行, n - 1个数表示斜向道路

Output

打印最少花费的狼保证能捕捉所有的羊

Sample Input Copy

3 4

5 6 4

4 3 1

7 5 3

5 6 7 8

8 7 6 5

5 5 5

6 6 6

Sample Output Copy

14

Source/Category