An và Bình là hai nhân viên phụ trách ánh sáng của nhà hát lớn Hà Nội. Công việc của họ là điều khiển ánh sáng cho các vở kịch. Sân khấu được xem như một hình chữ nhật kích thước , trên sân khấu có đèn chiếu sáng đặt ở vị trí khác nhau, sau mỗi cảnh An và Bình phải thay đổi lại trạng thái bật/tắt của các đèn trên sân khấu cho phù hợp với cảnh tiếp theo. An và Bình đã thống nhất, An sẽ đi bật những đèn đang tắt mà cảnh tiếp theo cần sáng, còn Bình sẽ đi tắt những đèn đang sáng cần phải tắt cho cảnh tiếp theo. An có tốc độ di chuyển là , Bình có tốc độ di chuyển là .
Trước mỗi vở kịch, An và Bình nhận được bản điều khiển ánh sáng chi tiết cho mỗi cảnh. Sau khi bố trí cho cảnh đầu tiên, An sẽ ở phía bên trái sân khấu, còn Bình ở phía bên phải sân khấu (hai bên sân khấu không liên thông với nhau). Sau mỗi cảnh, An và Bình sẽ chuẩn bị ánh sáng cho cảnh tiếp theo, giả thiết rằng An và Bình luôn chuẩn bị đứng ở vị trí tốt nhất khi đi vào sân khấu. Sau khi bật/tắt các đèn cho cảnh tiếp theo, An và Bình phải di chuyển về một trong hai bên sân khấu. Thời gian An (hoặc Bình) chuẩn bị cho một cảnh là tổng thời gian ra sân khấu đến các đèn để bật (hoặc tắt) các đèn, sau đó di chuyển về một trong hai bên sân khấu. Thời gian chuẩn bị cho một cảnh là thời gian hoàn thành của An và Bình. Hãy lên kế hoạch cho An và Bình để tổng thời gian giữa các cảnh là nhỏ nhất.
Dữ liệu:
Dòng đầu gồm số nguyên và ;
dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả tọa độ của từng đèn;
Dòng tiếp theo là số nguyên là số cảnh trong vở kịch;
dòng tiếp theo, mỗi dòng mô tả các đèn bật sáng trong từng cảnh có dạng:
Số đầu tiên là số là số đèn sẽ bật trong cảnh đó;
Tiếp theo là số, là chỉ số các đèn.
Kết quả:
Gồm một số duy nhất là tổng thời gian nhỏ nhất tìm được (đưa ra với độ chính xác chữ số sau dấu phẩy thập phân)$.
