while true do
    n, m = gets.split.map(&:to_i)
    break if n | m == 0
    dp = []
    stone = []
    for i in 0...n do
        line = gets.split.map(&:to_i)
        k = line.shift
        dp.push(Array.new(k) {Array.new(m+1, 1e10)})
        stone.push(Array.new(k) {line.shift(2)})
    end

    for i in 0..m do
        for j in 0...dp[i].size do
            dp[i][j][m-i] = 0
        end
    end

    for i in 0...n do
        for j in 0...dp[i].size do
            for k in 0..m do

                next if i+1 >= n
                for jj in 0...dp[i+1].size do
                    add = (stone[i+1][jj][1]+stone[i][j][1])*(stone[i+1][jj][0]-stone[i][j][0]).abs
                    dp[i+1][jj][k] = [dp[i+1][jj][k], dp[i][j][k]+add].min
                end

                next if (i+2 >= n) || (k-1 < 0)
                for jj in 0...dp[i+2].size do
                    add = (stone[i+2][jj][1]+stone[i][j][1])*(stone[i+2][jj][0]-stone[i][j][0]).abs
                    dp[i+2][jj][k-1] = [dp[i+2][jj][k-1], dp[i][j][k]+add].min
                end

            end
        end
    end

    ans = 1e10
    for j in 0...dp[n-1].size do
        ans = dp[n-1][j].min
    end
    puts ans

end