Touring Chef Residency Bonus

A traveling chef is booked for a D-day pop-up tour across K partner kitchens, numbered 0 through K-1. On each of the D days (numbered 0 through D-1), the chef -- currently working out of some kitchen -- must make exactly one of two choices:

• Stay at the current kitchen for that day, earning that day's nightly rating score for that kitchen.
• Relocate to a different kitchen, earning a one-time relocation bonus for that specific move (depending only on the origin and destination kitchen, never on the day), but earning no nightly rating for that day since the day was spent moving instead of cooking.

After relocating, the chef starts the next day already at the new kitchen. On day 0 the chef may begin at any kitchen of their choosing, with no cost or bonus for that initial placement. Determine the maximum total points the chef can accumulate over all D days.

Input format

• Line 1: two integers D and K -- the number of days and the number of kitchens.
• Next D lines: each contains K integers, where the j-th integer on the i-th of these lines is the nightly rating score for staying at kitchen j on day i.
• Next K lines: each contains K integers, where the j-th integer on the i-th of these lines is the one-time relocation bonus for moving from kitchen i to kitchen j (the diagonal entries, where i equals j, are always 0 and never used, since relocating to the kitchen you are already at is not a valid move).

Output format

A single integer: the maximum total points achievable over the D days.

Constraints

• 1 <= D <= 50
• 1 <= K <= 50
• every nightly rating score and relocation bonus is an integer with absolute value at most 1000

2 2
3 1
2 4
0 5
2 0

9

3 3
1 2 3
4 1 1
0 0 5
0 2 3
2 0 4
3 1 0

11