#1415. LASERS - Đồ chơi Lasers

Ông Panda biết mèo thích đồ chơi laser và quyết định đầu tư vào đồ chơi laser cho Rar the Cat. Đồ chơi laser mà ông Panda đã mua bao gồm các tia laser cách đều nhau ở đầu đồ chơi, hướng xuống dưới. Tia laser đầu tiên nằm cách mép ngoài cùng đơn vị và tia laser thứ nằm cách mép ngoài cùng bên phải của đồ chơi đơn vị. Mỗi laser liền kề có khoảng cách đơn vị.

Có hàng tường trượt, với mỗi hàng chứa một tập hợp các bức tường không chồng chéo. Chính xác, mỗi hàng chứa một số bức tường có tổng chiều dài tối đa . Các tường này có thể trượt đến bất kỳ vị trí nào trên cùng một hàng, miễn là các vị trí tương đối của chúng dọc theo hàng vẫn giữ nguyên và chúng không trùng nhau. Một bức tường có chiều rộng đơn vị (trong đó là số nguyên dương) sẽ chặn chính xác laser liên tiếp.

Một đồ chơi có thể có và được mô tả trong sơ đồ bên dưới:

Rar the Cat muốn biết: Trong số tia laser của đồ chơi, có bao nhiêu tia laser sẽ luôn bị chặn bởi ít nhất một bức tường trong tất cả các cấu hình có thể có của đồ chơi?

Dữ liệu vào:

• Dòng đầu tiên của đầu vào sẽ chứa hai số nguyên và ;
• Các dòng trong tiếp theo của đầu vào sẽ mô tả mỗi hàng. Nó sẽ bắt đầu với một số nguyên là số lượng tường trượt trong hàng. số nguyên theo sau, chỉ ra chiều rộng của các bức tường trong hàng đó, với số nguyên đầu tiên cho biết chiều rộng của bức tường ngoài cùng bên trái. Lưu ý rằng tổng chiều rộng của các bức tường trên mỗi hàng không thể vượt quá đơn vị .

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất trên một dòng là số lượng laser sẽ bị chặn bởi ít nhất một bức tường trong tất cả các cấu hình có thể có của đồ chơi.

Ví dụ:

Dữ liệu vào:

11 3
2 2 3
1 7
2 4 1

Dữ liệu ra:

3

Dữ liệu vào:

6 2
1 2 3 -10 5 6

Dữ liệu ra:

17

Dữ liệu vào:

6 4
-1 -2 -1 0 -5 -1

Dữ liệu ra:

0

Giới hạn:

• ở mỗi hàng.
• Subtask số điểm có ;
• Subtask số điểm khác có ;
• Subtask số điểm khác có ;
• Subtask số điểm khác có :
• Subtask số điểm khác có ;
• Subtask số điểm còn lại không có ràng buộc bổ sung.