Một trò chơi yêu cầu bạn nhảy qua các hòn đá để đi từ bờ này sang bờ kia của một con sông. Các hòn đá nằm trên một lưới có \(n\) hàng, đánh số từ bờ xuất phát đến bờ đối diện.

Một bước nhảy thông thường đưa bạn tới một hòn đá hoặc bờ ở hàng kế tiếp. Một bước nhảy vượt hàng đưa bạn tới một hòn đá hoặc bờ ở hàng cách hai hàng. Bạn được dùng không quá \(m\) bước nhảy vượt hàng.

Từ bờ xuất phát, hàng kế tiếp là hàng \(1\), hàng cách hai hàng là hàng \(2\). Từ hàng \(n-1\), một bước nhảy vượt hàng tới bờ đối diện; từ hàng \(n\), một bước nhảy thông thường tới bờ đối diện.

Mỗi hòn đá có một độ trơn. Độ nguy hiểm khi nhảy từ đá này sang đá khác, cho cả hai loại bước nhảy, bằng

Bước nhảy từ bờ tới đá hoặc từ đá tới bờ có độ nguy hiểm bằng \(0\).

Hãy tìm tổng độ nguy hiểm nhỏ nhất để sang bờ đối diện. Dữ liệu bảo đảm có thể sang được và không có hai hòn đá trong cùng một ô.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(n,m\), với \(2 \le n \le 150\), \(0 \le m \le \lfloor(n+1)/2\rfloor\).

Dòng thứ \(i+1\) mô tả hàng \(i\): bắt đầu bằng \(k_i\) (\(0 \le k_i \le 10\)), sau đó là \(k_i\) cặp \(x_{i,j},d_{i,j}\) lần lượt chỉ cột và độ trơn của từng hòn đá. Mọi số được phân cách bởi dấu cách. \(1 \le x_{i,j},d_{i,j} \le 1000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa tổng độ nguy hiểm nhỏ nhất.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm. \(20\%\) số điểm ứng với \(n \le 6\); một phần \(20\%\) khác ứng với \(m=0\).

Ví dụ

5 1
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

17

5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

40