In an alternate timeline Gamora still doesn't go right as Peter told her to and accidentally goes to a place called Gamoraland. People are clearly worried about her as seen below.

She noticed that this new place "Gamoraland" is full of other Gamoras.To differentiate this main Gamora, Let's call her GamoraX. She wants to be able to differentiate the other Gamoras from herself and thus decides to paint each of them with a colour that isn't green.

There are a total of n Gamoras excluding GamoraX (The one that didn't go right). The Gamoras are numbered with integers from 1 to n from left to right.

Initially, Gamora i has color c_i (Turns out someone already painted some Gamoras). GamoraX recognizes only m different colors, so 0 ≤ c_i ≤ m, where c_i = 0 means that Gamora i is Green.

GamoraX decides to color only the uncolored Gamoras, i.e. the green Gamoras (c_i = 0). She can color each of them them in any of the m colors from 1 to m. Exactly p_i, j litres of paint are required to paint the i-th Gamora with color j.

GamoraX defines the beauty of a coloring of the Gamoras as the minimum number of contiguous groups (each group contains some subsegment of Gamoras) you can split all the n Gamoras into so that each group contains Gamoras of the same color. For example, if the colors of the Gamoras from left to right are 1, 2, 2, 2, 3, 2, 2, 4, 4, 4, the beauty of the coloring is 5, since we can partition the Gamoras into 5 contiguous groups of the same color : {1}, {2, 2, 2}, {3}, {2, 2}, {4, 4, 4}.

GamoraX wants to color all uncolored Gamoras so that the beauty of the coloring is exactly k. They need your help to determine the minimum amount of paint (in litres) needed to finish the job.

Please note that GamoraX can't color the Gamoras that are already colored because that would be a waste of time and paint.

Input

The first line contains three integers, n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of Gamoras in Gamoraland, number of colors and beauty of the resulting coloring respectively.

The second line contains n integers c₁, c₂, ..., c_n (0 ≤ c_i ≤ m), the initial colors of the Gamoras. c_i equals to 0 if the Gamora number i is green, otherwise the i-th Gamora has color c_i.

Then n lines follow. Each of them contains m integers. The j-th number on the i-th line denotes p_i, j (1 ≤ p_i, j ≤ 10⁹) — the amount of litres the friends need to color i-th Gamora with color j. p_i, j's are specified even for the initially colored Gamoras, but such Gamoras still can't be colored.

Output

Print a single integer, the minimum amount of paint needed to color the Gamoras. If there are no valid Gamora colorings of beauty k, print  - 1