An mới mua một hộp đồ chơi laze. Hộp gồm ~R~ tia laze, tia đầu tiên cách mép trái của hộp 0,5 đơn vị độ dài, tia thứ ~R~ cách mép bên phải của hộp 0,5 đơn vị độ dài, hai tia liên tiếp cách nhau 1 đơn vị độ dài.

Có ~R~ đường ray trượt, trên mỗi ray trượt chứa một số các cánh cửa có thể trượt trên ray. Độ dài mỗi đường ray là ~L~ và tổng độ dài các cánh cửa trên mỗi đường ray không quá ~L~. Các cánh cửa thuộc đường ray nào có thể trượt trên đường ray đó nhưng tất nhiên không thể chồng lên nhau và không thể thay đổi thứ tự giữa các cánh cửa. Một cánh cửa với độ rộng ~x~ đơn vị (~x~ là số nguyên dương) có thể ngăn cản ~x~ tia laze liên tiếp.

Yêu cầu: Cho biết ~L, R~, số cánh cửa trên mỗi đường ray, độ rộng của mỗi cánh cửa và thứ tự các cánh cửa trên các ray. Hỏi có bao nhiêu tia laze không thể xuyên qua hộp trong bất kì trạng thái trượt nào của các cánh cửa.

Input

• Dòng đầu ghi số nguyên ~L, R~ (~1 \le L \le 10^9, 1 \le R \le 5 \cdot 10^5~);
• ~R~ dòng tiếp theo, mỗi dòng mô tả 1 đường ray trượt: bắt đầu bằng số nguyên ~X~ là số cánh cửa trên đường ray, tiếp theo là ~X~ số nguyên mô tả độ rộng các cánh cửa trên đường ray từ trái qua phải (dữ liệu đảm bảo tổng độ rộng các cánh cửa trên 1 đường ray không quá ~L~).
• Tổng các cánh cửa ở tất cả các đường ray ~\sum X \le 5 \cdot 10^5~.

Output

• Ghi ra một số nguyên duy nhất là số tia laze không thể xuyên qua hộp trong bất kì trạng thái trượt nào của các cánh cửa.