Alawn's Problem

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

Alawn has a length N array of pairs (a_i, b_i). Initially, a_i = b_i for all i.

Alawn loves arrays that satisfy the following property:

  • The a values can be sorted by only swapping elements i and j where b_i \times b_j \le V.

A modification to the array consists of decreasing element i's b_i value by 1. Can you determine the minimum number of modifications required to turn the array of pairs into one that Alawn loves?

Input Specification

The first line will contain T (1 \le T \le 10), the number of test cases. T test cases follow.

For each test case, the first line will contain two integers N, V (1 \le N \le 10^5, 1 \le V \le 10^{18}), the number of elements in the array and the special value V.

The second line will contain N integers, a_i (1 \le a_i \le 10^9), the elements of the array. Recall that a_i = b_i initially.

Output Specification

For each case, output the minimum number of modifications required on its own line.

Sample Input

2
5 1
1 2 3 4 5
5 4
1 2 5 3 6

Sample Output

0
1

Comments

There are no comments at the moment.