아야는 쇼핑몰을 거닐다 가챠 머신 하나를 발견했습니다. 가챠 머신에는 총 $n$ 종류의 가챠가 있으며, $i$번째 종류의 가챠는 $a_i$개 있습니다.

• 가챠 코인 하나를 소비하여 가챠 하나를 무작위로 얻을 수 있습니다.
• 임의의 가챠 $k$개를 소비하여 상점으로부터 지정 코인 하나로 교환할 수 있습니다.
• 지정 코인 하나를 소비하여 가챠 머신에서 원하는 종류의 가챠 하나를 얻을 수 있습니다.

모든 가챠는 다시 머신에 넣지 않습니다. 아야는 $n$ 종류의 가챠를 모두 모으고 싶어 합니다. 즉, 마지막에 각 종류의 가챠를 최소 하나씩 보유하고자 합니다. 이때 $n$ 종류의 가챠를 모두 모으기 위해 보장된 최소 가챠 코인 개수를 구하세요.

입력

본 문제는 여러 개의 테스트 케이스로 구성되어 있습니다. 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 3000$)가 주어집니다.

각 테스트 케이스에 대하여: 첫 번째 줄에 두 정수 $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$)가 주어지며, 각각 가챠의 종류 수와 지정 코인으로 교환하는 데 필요한 가챠의 개수를 의미합니다. 두 번째 줄에 $n$개의 정수가 주어지며, $i$번째 정수 $a_i$ ($1 \le a_i \le 3000$)는 $i$번째 종류 가챠의 개수를 의미합니다.

모든 테스트 케이스의 $n$의 합은 $3000$을 넘지 않습니다.

출력

각 테스트 케이스마다 $n$ 종류의 가챠를 모두 모으기 위해 보장된 최소 가챠 코인 개수를 한 줄에 출력합니다.

예제

입력 1

2
2 2
1 4
4 3
8 7 6 5

출력 1

3
9