import Control.Monad (replicateM)
import Data.Array (Array,listArray,(!),(//))

type Column = Int
type Danger = Int
type Stone = (Column,Danger)

type Point = Int
type PointMatrix = Array Int [Point]

main = do
    [n,m] <- getLine >>= return . map read . words
    if all (==0) [n,m] then return () else do
        st <- readStones n
        print $ solve m st
        main

readStones :: Int -> IO [[Stone]]
readStones n = replicateM n readRow
    where
    readRow = do
        nums <- getLine >>= return . map read . words
        return (stones (tail nums))

    stones [] = []
    stones (c:d:ns) = (c,d) : stones ns

solve :: Int -> [[Stone]] -> Point
solve m (r2:r1:rs) = pm1 `seq` pm2 `seq` step rs r1 r2 pm1 pm2
    where
    pm2 = (listArray (0,m) (repeat [])) // [(m, map (const 0) r2)]

    pm1 | m == 0 = (listArray (0,m) (repeat [])) //
            [(m, ((r2,pm2) %% m) <*> r1)]
        | otherwise = (listArray (0,m) (repeat [])) //
            [(m, ((r2,pm2) %% m) <*> r1), (m-1, map (const 0) r1)]

    step [] r1 r2 pm1 pm2 = case (ps1,ps2) of
            ([],[]) -> -1
            (ps,[]) -> minimum ps
            ([],ps) -> minimum ps
            (ps1,ps2) -> min (minimum ps1) (minimum ps2)
        where
        ps1 = concatMap (pm1!) [0..m]
        ps2 = concatMap (pm2!) [1..m]

    step (r0:rs) r1 r2 pm1 pm2 = pm0 `seq` step rs r0 r1 pm0 pm1
        where
        pm0 = listArray (0,m) (map points [0..m])
        points m'
            | m' == m = ((r1,pm1) %% m') <*> r0
            | otherwise = takeMin
                    (((r1,pm1) %% m') <*> r0)
                    (((r2,pm2) %% (m'+1)) <*> r0)

        takeMin [] xs = xs
        takeMin xs [] = xs
        takeMin xs ys = zipWith min xs ys

    (%%) :: ([Stone],PointMatrix) -> Int -> [(Stone,Point)]
    (r,pm) %% m = zip r (pm!m)

    (<*>) :: [(Stone,Point)] -> [Stone] -> [Point]
    [] <*> _ = []
    prevs <*> currs = map safest currs
        where
        safest curr = minimum $ map (`newPoint` curr) prevs
        newPoint ((c1,d1),p1) (c0,d0) = p1 + (d0+d1) * (abs (c0-c1))