Fill the boxes

3.4

9 votes
Problem

You are given an array of size N, denoting capacity of N boxes, and an integer K, denoting extended capacity factor. You are also given the weights of M balls. Each ith box can accommodate exactly one ball having weight in range [capacityi,capacityi+K] (both inclusive). Find the maximum number of boxes that can be filled.

Constraints:

  • 1T50
  • 1N,M10000
  • 1K1000
  • 1Capacityi1000
  • 1Weighti2000

Input format:
First line: T i.e. Number of test cases.
For each test case:
First line: Three space-separated integers N, M and K.
Second line: N space-separated integers denoting the capacity of boxes.
Third line: M space-separated integers denoting the weight of balls.

Output format:
For each test case, print the answer in a separate line.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In best scenario we can put ball 2 in box 1 hence answer is 1.

Editor Image

?