Những người lớn tuổi vẫn nhớ trò chơi nổi tiếng TETRIS do Alexey Pajitnov sáng tạo. Trong trò chơi đó, những mảnh ghép gồm bốn ô vuông rơi xuống; người chơi xoay và xếp chúng vào một khung chữ nhật để tạo ra nhiều hàng đầy nhất có thể. Mỗi hàng không còn ô trống sẽ biến mất, nhường chỗ cho các mảnh tiếp theo.

Hãy xét một phiên bản đơn giản hơn, gọi là Tiny TETRIS, hay Tiny. Trò chơi chỉ có chín loại mảnh, mỗi mảnh gồm từ một đến ba ô vuông:

Các số trong hình là số hiệu dùng để chỉ từng loại mảnh. Khung chơi có chiều rộng \(9\) và chiều cao \(9\) ô. Các mảnh không được xoay, và cũng không được dịch sang trái hoặc phải sau khi bắt đầu rơi. Với mỗi mảnh, người chơi chỉ chọn số hiệu cột, từ \(1\) đến \(9\), mà ô ngoài cùng bên trái của mảnh, được đánh dấu bằng dấu \(\times\), sẽ rơi vào.

Mỗi ván gồm một dãy hữu hạn \(N\) mảnh. Mục tiêu là thả được nhiều mảnh nhất vào khung mà không vượt quá mép trên và không thực hiện nước đi không hợp lệ. Kết quả của ván chơi là số mảnh đã thả thành công.

Bộ đếm ban đầu bằng \(0\). Trò chơi diễn ra như sau:

1. Người chơi chọn cột cho ô ngoài cùng bên trái của mảnh hiện tại.
2. Nếu cột được chọn hợp lệ, mảnh rơi thẳng xuống cho tới khi gặp chướng ngại vật. Nếu không, ván chơi kết thúc. Chẳng hạn, cột \(8\) luôn không hợp lệ với mảnh loại \(5\) vì mảnh sẽ vượt ra ngoài khung bên phải.
3. Nếu toàn bộ các ô của mảnh nằm trong khung \(9\times9\), bộ đếm tăng thêm \(1\). Nếu không, ván chơi kết thúc.
4. Kiểm tra các hàng ngang đã được lấp đầy. Mọi hàng đầy biến mất, và các hàng phía trên dồn xuống mà không thay đổi cách sắp xếp các ô trong từng hàng.
5. Nếu vẫn còn mảnh, quay lại bước \(1\). Nếu đã hết mảnh, ván chơi kết thúc.

Kết quả của ván chơi là giá trị bộ đếm khi ván kết thúc.

Dữ liệu vào

Đây là bài chỉ nộp kết quả, với dữ liệu vào công khai. Có đúng năm tệp dữ liệu: tiny.i1, tiny.i2, tiny.i3, tiny.i4 và tiny.i5.

Trong mỗi tệp, dòng đầu chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên từ \(1\) đến \(9\), là số hiệu một mảnh. Các mảnh được liệt kê theo đúng thứ tự phải thả; mảnh thứ \(i\) nằm trên dòng \(i+1\).

Dữ liệu ra

Nộp một tệp ZIP chứa đúng năm tệp tiny.o1, tiny.o2, tiny.o3, tiny.o4 và tiny.o5 ngay ở thư mục gốc của ZIP. Tệp tiny.ok chứa kết quả cho tiny.ik, với \(k\) từ \(1\) đến \(5\).

Mỗi tệp kết quả có nhiều nhất \(N\) dòng. Dòng thứ \(i\) chứa đúng một số hiệu cột từ \(1\) đến \(9\), cho biết cột thả mảnh thứ \(i\). Có thể nộp một tiền tố của dãy nước đi; nếu không ghi nước đi nào thì tệp tương ứng rỗng. Không ghi số lượng nước đi ở đầu tệp. Khi một nước đi làm ván chơi kết thúc, chỉ những mảnh đã được thả thành công trước đó được tính.

Ràng buộc

• Mỗi mảnh thuộc một trong chín loại trong hình.
• Năm tệp lần lượt có \(N=1000,5000,20\,000,50\,000,100\,000\) mảnh.
• Với mỗi tệp, bảo đảm tồn tại một dãy cột giúp thả thành công toàn bộ \(N\) mảnh.

Phân nhóm

• tiny.i1: tối đa \(20\) điểm.
• tiny.i2: tối đa \(20\) điểm.
• tiny.i3: tối đa \(20\) điểm.
• tiny.i4: tối đa \(20\) điểm.
• tiny.i5: tối đa \(20\) điểm.

Gọi \(K\) là số mảnh thả thành công. Trong kỳ thi gốc, điểm cuối cùng của mỗi tệp được tính theo công thức

rồi làm tròn đến hai chữ số sau dấu thập phân. Trong thời gian thi, thí sinh được thông báo \(K\) và mức điểm bảo đảm, với giả thiết có người thả được đủ \(N\) mảnh. Sau kỳ thi, điểm được tính lại theo kết quả tốt nhất thực tế nên có thể tăng lên.

Ở bài luyện tập này, điểm được cố định theo đúng mức điểm bảo đảm đó:

Ví dụ

20
5
4
1
6
7
6
4
4
7
9
5
5
6
8
3
4
3
7
4
2

1
2
2
4
8
8
7
4
8
6
1
1
4
8
3
7
7