Bạn đang theo một giáo án tập cử tạ định sẵn. Giáo án gồm một chuỗi các bài tập mà bạn phải thực hiện theo đúng thứ tự. Mỗi bài tập yêu cầu đặt một bộ tạ cụ thể lên máy.

Có \(\mathbf{W}\) loại tạ khác nhau. Chẳng hạn, một bài tập có thể cần \(3\) đĩa tạ loại A và \(1\) đĩa tạ loại B, còn bài tập kế tiếp cần mỗi loại A, C và D đúng \(2\) đĩa.

Các đĩa tạ được đặt trên máy thành một chồng. Chính xác hơn, trong một thao tác, bạn có thể thêm một đĩa tạ thuộc loại bất kỳ lên đỉnh chồng, hoặc lấy đĩa tạ hiện nằm trên đỉnh chồng ra.

Bạn có thể chất các đĩa tạ cần cho từng bài tập lên máy theo thứ tự tùy ý. Vì vậy, nếu ở bài tập đầu trong ví dụ trên bạn đặt đĩa loại B ở đáy, bạn sẽ phải lấy hết các đĩa ra trước khi đặt tạ cho bài tập thứ hai. Ngược lại, nếu đặt đĩa loại B ở vị trí thứ ba tính từ đáy, bạn có thể giữ lại hai đĩa loại A ở đáy chồng để dùng trong bộ tạ của bài tập tiếp theo, qua đó tiết kiệm thời gian.

Biết số lượng tạ của từng loại mà mỗi bài tập cần, hãy tìm số thao tác ít nhất để hoàn thành tất cả. Bạn phải thực hiện các bài tập theo thứ tự đã cho. Ban đầu chồng tạ trên máy rỗng, và sau khi hoàn thành mọi bài tập bạn cũng phải để chồng tạ rỗng.

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(\mathbf{T}\). Tiếp theo là \(\mathbf{T}\) bộ test.

Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(\mathbf{E}\) và \(\mathbf{W}\): số bài tập và số loại tạ. Các loại tạ được đánh số từ \(1\) đến \(\mathbf{W}\).

Tiếp theo là \(\mathbf{E}\) dòng. Dòng thứ \(i\) chứa \(\mathbf{W}\) số nguyên \(\mathbf{X}_{i,1},\mathbf{X}_{i,2},\ldots,\mathbf{X}_{i,\mathbf{W}}\), nghĩa là bài tập thứ \(i\) cần chính xác \(\mathbf{X}_{i,j}\) đĩa tạ loại \(j\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là số thao tác trên chồng tạ của máy ít nhất cần dùng để hoàn thành toàn bộ các bài tập.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(1 \le \mathbf{X}_{i,1}+\mathbf{X}_{i,2}+\dots+\mathbf{X}_{i,\mathbf{W}}\) với mọi \(i\); tức mỗi bài tập cần ít nhất một đĩa tạ.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le\mathbf{E}\le10\), \(1\le\mathbf{W}\le3\), và \(0\le\mathbf{X}_{i,j}\le3\) với mọi \(i,j\).
• Test Set 2 (phán quyết ẩn): \(1\le\mathbf{E}\le100\), \(1\le\mathbf{W}\le100\), và \(0\le\mathbf{X}_{i,j}\le100\) với mọi \(i,j\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3 1
1
2
1
2 3
1 2 1
2 1 2
3 3
3 1 1
3 3 3
2 3 3

Case #1: 4
Case #2: 12
Case #3: 20

Nguồn

Google Code Jam 2022, Vòng 1A, bài Weightlifting.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.