Banner

V là sinh viên khoa Công nghệ Thông tin trường Đại học H. Ngoài những giờ chạy deadline "nhẹ nhàng", V còn có sở thích chơi Genshin Impact.

Mỗi mùa, nhà phát hành của Genshin Impact - Mihoyo - sẽ cho ra mắt các nhân vật mới với kỹ năng chiến đấu đỉnh cao và ngoại hình đẹp mắt. Trước khi ra mắt nhân vật, Mihoyo sẽ công bố danh sách nhân vật mới mà người chơi có thể nhận được mỗi ngày. Trong trò chơi này, để nhận được một nhân vật nào đó, người chơi cần thực hiện hành động "cầu nguyện". Vì gọi là "cầu nguyện" nên hành động này mang tính "may rủi" và thường người chơi sẽ không thể nhận được ngay nhân vật mình mong muốn.

Tuy nhiên, là một người chơi lâu năm dày dạn kinh nghiệm, V đã tính toán được quy luật của từng mùa: với nhân vật thứ $i$, người chơi chỉ cần cầu nguyện p_i lần thì chắc chắn sẽ nhận được nhân vật; nếu số lần cầu nguyện ít hơn p_i, người chơi chắc chắn không thể có được nhân vật đó.

Mỗi ngày trong một mùa bất kỳ, V có 2 lựa chọn: hoặc không thực hiện cầu nguyện và nhận 1 lượt cầu nguyện (được tích lũy cho các ngày sau), hoặc dùng một số lượt cầu nguyện đã tích lũy cho nhân vật xuất hiện vào ngày hôm đó. Khi đã nhận được một nhân vật, V sẽ sở hữu nhân vật này trong suốt cả mùa và không cần phải cầu nguyện lại nữa. Tuy nhiên, mỗi khi bước sang mùa mới, V lại bán tài khoản cũ và tạo tài khoản mới (chưa có nhân vật nào) để trang trải học phí vì V vẫn là một sinh viên phải ăn mì gói vào cuối tháng. Do còn cần luyện tập sử dụng các nhân vật mới để chinh phục La Hoàn Thâm Cảnh, V muốn sở hữu tất cả nhân vật càng sớm càng tốt. Bạn hãy giúp V tính số ngày tối thiểu cần thiết để có được toàn bộ nhân vật trong từng mùa nhé!

Đầu vào: Dòng đầu tiên chứa số nguyên T - số lượng mùa mà Mihoyo đã công bố danh sách nhân vật.

Tiếp theo là mô tả của T mùa, mỗi mùa gồm:

• Dòng đầu tiên chứa số nguyên c là số lượng nhân vật mới trong mùa này.

• c dòng tiếp theo là danh sách nhân vật của mùa này. Dòng thứ $i$ ($1 \leq i \leq c$) chứa một xâu ký tự s_i và một số nguyên p_i lần lượt là tên nhân vật và số lượt cầu nguyện để nhận được nhân vật đó. Dữ liệu đảm bảo không có hai nhân vật nào trùng tên và tên nhân vật chỉ gồm các chữ cái Latin.

• Dòng tiếp theo chứa số nguyên d là số ngày của mùa.

• d dòng tiếp theo, mỗi dòng chứa một xâu ký tự là tên nhân vật mà người chơi có thể nhận được trong ngày hôm đó. Nếu là xâu "No character" thì nghĩa là không có nhân vật nào xuất hiện vào ngày hôm đó.

Giới hạn

• $1 \leq T \leq 10$
• $1 \leq c \leq 50$
• $1 \leq d \leq 10^5$
• $1 \leq |s_i| \leq 10$, $1 \leq p_i \leq d$ (với $1 \leq i \leq c$)

Đầu ra: Gồm T dòng tương ứng với T mùa, trên mỗi dòng:

• In ra "Impossible" nếu V không có cách nào sở hữu toàn bộ c nhân vật trong mùa đó.
• Ngược lại, in ra một số nguyên duy nhất là số ngày tối thiểu V cần để sở hữu tất cả các nhân vật trong mùa Genshin Impact đó.

Giải thích: V sẽ cầu nguyện và nhận được Nahida vào ngày thứ ba và Diluc vào ngày thứ năm. Do đó, V mất tối thiểu 5 ngày để có được cả 2 nhân vật của mùa này.

Ví dụ 1:

Đầu vào:

1
2
Diluc 2
Nahida 1
6
Diluc
No character
Nahida
No character
Diluc
Nahida

Đầu ra:

5