{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problem statements in [Hindi](https://www.codechef.com/download/translated/LTIME93/hindi/DIV03.pdf), [Bengali](https://www.codechef.com/download/translated/LTIME93/bengali/DIV03.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/LTIME93/mandarin/DIV03.pdf), [Russian](https://www.codechef.com/download/translated/LTIME93/russian/DIV03.pdf), and [Vietnamese](https://www.codechef.com/download/translated/LTIME93/vietnamese/DIV03.pdf) as well.\r\n\r\nDaanish as always is busy creating and solving his favourite and interesting graph problems. Chef assigns each problem a difficulty — an integer between $1$ and $10$. For each valid $i$, there are $A_i$ problems with difficulty $i$.\r\n\r\nA participant hacked Daanish\u0027s account and got access to the problem proposal document. He can delete up to $K$ problems from the document in order to reduce the difficulty of the contest for himself and his friends. Find the smallest possible value of the difficulty of the most difficult problem which remains after removing $K$ problems.\r\n\r\n### Input\r\n- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\r\n- The first line of each test case contains $10$ space-separated integers $A_1, A_2, \\ldots, A_{10}$.\r\n- The second line contains a single integer $K$.\r\n\r\n### Output\r\nFor each test case, print a single line containing one integer — the minimum difficulty of the most difficult remaining problem.\r\n\r\n### Constraints\r\n- $1 \\leq T \\leq 2 \\cdot 10^4$\r\n- $0 \\leq A_i \\leq 10^8$ for each valid $i$\r\n- $A_1 + A_2 + \\ldots + A_{10} \\gt 0$\r\n- $0 \\leq K \\lt A_1 + A_2 + \\ldots + A_{10}$\r\n\r\n### Subtasks\r\n**Subtask #1 (100 points):** original constraints"}},{"title":"Sample 1","value":{"format":"MD","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\u003e5\r\n1 10 1 5 3 2 4 9 0 100\r\n100\r\n2 0 1 0 0 0 0 0 0 10\r\n12\r\n2 0 1 0 0 0 0 10 0 0\r\n0\r\n2 0 1 0 0 0 0 0 0 10\r\n10\r\n1 10 1 5 3 2 4 9 0 100\r\n125\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\r\n1\r\n8\r\n3\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n**Example case 1:** The participant can remove all $100$ problems with difficulty $10$. Then, there are no problems with difficulties $9$ and $10$, so the maximum difficulty among remaining problems is $8$.\r\n\r\n**Example case 2:** The participant can remove all problems with difficulties $3$ and $10$ and any one of the problems with difficulty $1$. Then, the only problem left has difficulty $1$.\r\n\r\n**Example case 3:** The participant cannot remove any problem. The document does not contain any problems with difficulties $9$ or $10$, so the maximum difficulty of a problem is $8$."}}]}