#1471. WOOD - Căt gỗ

Hùng vừa cắt một tấm gỗ mỏng hình chữ nhật thành nhiều miếng hình chữ nhật. Máy cưa cậu dùng mỗi lần sẽ nhận vào một miếng gỗ hình chữ nhật và cắt làm hai hình chữ nhật với tổng diện tích không đổi. Vị trí cắt có thể điều chỉnh được, chi phí cắt phụ thuộc vào trọng lượng miếng gỗ, do miếng gỗ ban đầu có độ dày đồng đều nên chi phí cắt có thể xem là diện tích miếng gỗ đó.

Miếng gỗ ban đầu có kích thước . Hùng đã dùng bút vẽ đường kẻ ngang và đường kẻ dọc, kết hợp với các đường biên chia hình chữ nhật thành một lưới tọa độ. Các điểm được đánh tọa độ từ đến từ trên xuống dưới, từ trái qua phải. Các lát cắt đều song song với biên và được đánh dấu bởi tọa độ các điểm này. Mỗi lát cắt là một đường liên tục và cắt dứt điểm một miếng nào đó làm hai phần. Miếng gỗ ban đầu đã được cắt xong, Hùng cần báo cáo lại quá trình cắt. Cậu nhớ chính xác tọa độ tất cả các lát cắt mà mình thực hiện, tuy nhiên không nhớ chính xác thứ tự đã cắt. Hùng đưa cho bạn danh sách các lát cắt này và nhờ bạn sắp xếp lại thứ tự cho hợp lý. Cậu cũng biết rằng có thể có nhiều thứ tự khác nhau, và quả quyết rằng trong số các thứ tự đúng đó, mình đã cắt theo một thứ có tổng chi phí cắt là nhỏ nhất.

Yêu cầu: Hãy giúp Hùng tìm ra một thứ tự cắt (tức hoán vị các lát cắt theo trí nhớ của Hùng) hợp lý và có tổng chi phí nhỏ nhất, hoặc thông báo là cậu đã nhớ nhầm.

Dữ liệu vào:

• Dòng đầu chứa ba số nguyên dương là kích thước ban đầu và số lát cắt: ;
• dòng tiếp theo, mỗi dòng ghi một lát cắt: có nghĩa lát cắt này kéo dài từ điểm đến điểm . Dữ liệu đảm bảo lát cắt song song với biên, không trùng lên biên của hình chữ nhật đang cắt và có độ dài khác .

Dữ liệu ra:

Nếu không có thứ tự nào hợp lý, in ra . Ngược lại in ra trên hai dòng:

• Dòng đầu chứa chi phí cắt nhỏ nhất tìm được;
• Dòng tiếp theo chứa số là một hoán vị của cho biết thứ tự các lát cắt tìm được.

Dữ liệu đảm bảo chi phí nhỏ nhất nếu có sẽ không vượt quá .

Ví dụ:

Dữ liệu vào:

5 10 11
3 5 5 5
3 0 3 10
0 5 3 5
1 5 1 10
2 5 2 10
4 5 4 10
3 1 5 1
3 2 5 2
3 3 5 3
3 4 5 4
1 8 2 8

Dữ liệu ra:

164
2 1 3 4 5 6 8 7 9 11 10

Giới hạn:

Với mỗi test, nếu chỉ tính đúng chi phí cắt sẽ được điểm của test đó, để nhận được điểm này thì dòng thứ hai bạn cần để trống.

• Subtask số điểm có ;
• Subtask số điểm khác có ;
• Subtask số điểm khác có thứ tự Hùng nhớ là một thứ tự hợp lý và tối ưu;
• Subtask số điểm khác có Thứ tự Hùng nhớ là một thứ tự hợp lý;
• Subtask còn lại có Ràng buộc gốc.