CF1856C To Become Max

You are given an array of integers $ a $ of length $ n $ . In one operation you: - Choose an index $ i $ such that $ 1 \le i \le n - 1 $ and $ a_i \le a_{i + 1} $ . - Increase $ a_i $ by $ 1 $ . Find the maximum possible value of $ \max(a_1, a_2, \ldots a_n) $ that you can get after performing this operation at most $ k $ times.

Each test contains multiple test cases. The first line of input contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 1000 $ , $ 1 \le k \le 10^{8} $ ) — the length of the array $ a $ and the maximum number of operations that can be performed. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 10^{8} $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ .

For each test case output a single integer — the maximum possible maximum of the array after performing at most $ k $ operations.

In the first test case, one possible optimal sequence of operations is: $[\textcolor{red}{1}, 3, 3] \rightarrow [2, \textcolor{red}{3}, 3] \rightarrow [\textcolor{red}{2}, 4, 3] \rightarrow [\textcolor{red}{3}, 4, 3] \rightarrow [4, 4, 3]$. In the second test case, one possible optimal sequence of operations is: $[1, \textcolor{red}{3}, 4, 5, 1] \rightarrow [1, \textcolor{red}{4}, 4, 5, 1] \rightarrow [1, 5, \textcolor{red}{4}, 5, 1] \rightarrow [1, 5, \textcolor{red}{5}, 5, 1] \rightarrow [1, \textcolor{red}{5}, 6, 5, 1] \rightarrow [1, \textcolor{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$.