Duyệt binh

Có $n$ loại chiều cao, được đánh số từ $1$ đến $n$. Với mỗi $i$, có $c_i$ người lính chiều cao $i$.

Cần chọn ra một số người lính và xếp họ vào $k$ hàng sao cho:

• Mọi hàng đều có cùng số người.
• Trong mỗi hàng, chiều cao của hai người lính bất kỳ chênh lệch nhau không quá $1$ (tức là một hàng chỉ chứa người lính có chiều cao $h$ hoặc $h+1$ với một $h$ nào đó).

Hãy tính số người lính lớn nhất có thể tham gia duyệt binh.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ:
  • Dòng đầu chứa hai số nguyên $n$ và $k$.
  • Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên — số người lính lớn nhất có thể tham gia duyệt binh.

Ràng buộc

• $1\le t\le 10000$
• $1\le n\le 30000$
• $1\le k\le {10}^{12}$
• $0\le c_i\le {10}^{12}$
• Tổng $n$ qua tất cả bộ dữ liệu không vượt quá $30000$.

Ví dụ