{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"![Image Text](CDN_BASE_URL/0d6e49960f5ef3a5e58b4fb124dd18d6?v\u003d1716058666)\n\n**Agent 47** is in a dangerous Mission \"Black Monster Defeat - 15\". It is a secret mission and so 47 has a limited supply of weapons. He has only one weapon the old weak \"**KM .45 Tactical (USP)\"**. The mission sounds simple - he will encounter at most 15 Targets and he has to kill them all. The main difficulty is the weapon. After a lot of calculations, he found a way out. After defeating a target, he can use the target\u0027s weapon to kill other targets. So there must be an order of killing the targets so that the total number of weapon shots is minimal. As a personal programmer of Agent 47 you have to calculate the least number of shots that need to be fired to kill all the targets.\n\nNow you are given a list indicating how much damage each weapon does to each target per shot, and you know how much health each target has. When a target\u0027s health is reduced to **0** or less, he is killed. **47** start off only with the **KM .45 Tactical (USP)**, which does damage **1** per shot to any target. The list is represented as a **2D** matrix with the **i\u003csup\u003eth\u003c/sup\u003e** element containing **N** single-digit numbers **(\u00270\u0027-\u00279\u0027)**, denoting the damage done to targets **0, 1, 2, ..., N-1** by the weapon obtained from target **i**, and the health is represented as a series of **N** integers, with the **i\u003csup\u003eth\u003c/sup\u003e** element representing the amount of health that target has.\n\nGiven the list representing all the weapon damages, and the health each target has, you should find the least number of shots he needs to fire to kill all of the targets."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 40)**, denoting the number of test cases.\n\nEach case begins with a blank line and an integer **N (1 \u0026#8804; N \u0026#8804; 15)**. The next line contains **N** space separated integers between **1** and **10\u003csup\u003e6\u003c/sup\u003e** denoting the health of the targets **0, 1, 2, ..., N-1**. Each of the next **N** lines contains **N** digits. The **j\u003csup\u003eth\u003c/sup\u003e** digit of the **i\u003csup\u003eth\u003c/sup\u003e** line denotes the damage done to target **j**, if you use the weapon of target **i** in each shot."}},{"title":"Output","value":{"format":"MD","content":"For each case of input you have to print the case number and the least number of shots that need to be fired to kill all of the targets."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\n3\n10 10 10\n010\n100\n111\n\n3\n3 5 7\n030\n500\n007\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 30\nCase 2: 12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}