import           Control.Monad
import qualified Data.Array.IArray as A
import qualified Data.Map          as M

main :: IO ()
main = do
  [n, c] <- getInts
  ds <- replicateM c getInts
  cs <- replicateM n getInts
  let dat = makeMap c ds
      cls = colorTab n c cs
  print $ solve c dat cls

getInts :: IO [Int]
getInts = map read . words <$> getLine

makeMap n xs = let idx = map (\[a, b] -> (a, b)) $ replicateM 2 [1..n]
               in M.fromList $ zip idx $ concat xs

colorTab :: Int -> Int -> [[Int]] -> A.Array (Int, Int) Int
colorTab n c xs = let idx = map (\[a, b] -> (a + b) `mod` 3) $ replicateM 2 [1..n]
                  in A.accumArray (+) 0 ((0, 1), (2, c)) $ zip (zip idx $ concat xs) $ repeat 1

solve c dat cls = foldr (\a b -> if null a then b else min (sum a) b) (2^30) ans
  where ans = do
          [i, j, k] <- replicateM 3 [1..c]
          if i == j || i == k || j == k
            then return []
            else return $ map (uncurry calc) $ zip [0..2] [i, j, k]
            where
              calc idx color = let ns = map (\(ix, cl) -> (cl, cls A.! (ix, cl))) $ zip (repeat idx) [1..c]
                               in foldr (\(cl, n) b -> b + (dat M.! (cl, color)) * n) 0 ns
