INF = 1<<29
n, m = gets.split.map(&:to_i)
s = n.times.map { gets.split.map(&:to_i)[1..-1].each_slice(2).to_a }
c = s.flatten(1).transpose[0].max

dp = (n+1).times.map { (m+1).times.map { [INF] * (c+1) } }
(m+1).times{ |i| dp[0][i].fill(0) }

(n-1).times do |i|
  (m+1).times do |j|
    s[i].each do |k, d0|
      s[i+1].each do |l, d1|
        x = dp[i][j][k] + (l - k).abs * (d0 + d1)
        dp[i+1][j][l] = x if dp[i+1][j][l] > x
      end
    end
  end
  next if i == n - 2
  m.times do |j|
    s[i].each do |k, d0|
      s[i+2].each do |l, d1|
        x = dp[i][j][k] + (l - k).abs * (d0 + d1)
        dp[i+2][j+1][l] = x if dp[i+2][j+1][l] > x
      end
    end
  end
end
p dp[n-1,2].flatten.min