import java.lang.Math.abs

fun main(args:Array<String>):Unit {
    while (true) {
        val (n, m) = readLine()!!.trim().split(' ').map(String::toInt)
        if (n == 0 && m == 0) return
        val stones = Array(n){
            val a = readLine()!!.trim().split(' ').map(String::toInt).toIntArray()
            (1 .. a[0]).map{
                Stone(a[it * 2 - 1], a[it * 2])
            }.toTypedArray()
        }
        val dangers = stones.map{
            Array(it.size){Array(m + 1){Int.MAX_VALUE}}
        }.toTypedArray()
        for (i in 0 until dangers[0].size){
            dangers[0][i][m] = 0
        }
        if (m > 0) for (i in 0 until dangers[1].size){
            dangers[1][i][m - 1] = 0
        }
        for (line in 1 until n){
            for (from in 0 until dangers[line - 1].size){
                for (to in 0 until dangers[line].size){
                    for (d in 0 .. m){
                        if (dangers[line][to][d] - stones[line - 1][from].jumpTo(stones[line][to]) > dangers[line - 1][from][d]){
                            dangers[line][to][d] = dangers[line - 1][from][d] + stones[line - 1][from].jumpTo(stones[line][to])
                        }
                    }
                }
            }
            if (line > 1){
                for (from in 0 until dangers[line - 2].size){
                    for (to in 0 until dangers[line].size){
                        for (d in 1 .. m){
                            if (dangers[line][to][d - 1] - stones[line - 2][from].jumpTo(stones[line][to]) > dangers[line - 2][from][d]){
                                dangers[line][to][d - 1] = dangers[line - 2][from][d] + stones[line - 2][from].jumpTo(stones[line][to])
                            }
                        }
                    }
                }
            }
        }
        val l = dangers.takeLast(2)
        println(
                minOf(l.first().map{
                    it.drop(1).min() ?: Int.MAX_VALUE
                }.min() ?: Int.MAX_VALUE, l.last().map{it.min() ?: Int.MAX_VALUE}.min() ?: Int.MAX_VALUE)
        )
    }
}
data class Stone(val x:Int, val danger:Int){
    fun jumpTo(stone:Stone):Int {
        return abs(x - stone.x) * (danger + stone.danger)
    }
}
