JLNT - Jarin Loves New Task

no tags 


Jarin has got a new task. She has to connect towers by wire.


  1. Number of towers N (2<=N<=1000)
  2. The length of wire L (0<=L<=5000).
  3. Coordinates of each tower in 1D starting from left to right and each coordinate will be a positive distinct integer (0<=a[i]<=5000).

Her task is to maximize the number of connected towers using that wire. But she has to make sure each tower is either connected with its left tower or its right tower or have no connection. She has to cut off the wire into particular sizes she wants to use.


It so difficult task for her. So you must have to help her :) . 


Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with two integers N and L .  Next line contains N space separated integers.


For each case, print the case number and expected answer.

Sample Input

Output for Sample Input


6 2

1 2 3 4 5 6

Case 1: 4


Problem Setter: Ajharul Islam Barid

Special Thanks: Abu Zafar Newton.

hide comments
Jacob Plachta: 2014-10-15 08:32:01

To clarify, not all of the wire must be used, and a tower cannot be connected both on its left and on its right.

Last edit: 2014-10-15 08:34:55
Ajharul Islam Barid: 2014-10-14 10:25:23

Coordinates strictly positive.

RE: There are certainly values of 0, unless there's something more wrong with the input.

Last edit: 2014-10-09 09:59:19
Ajharul Islam Barid: 2014-10-14 10:25:23

6 1
1 2 3 4 5 6
cheak this case

RE: The answer should surely be 2, right? Or is that not what the problem's asking?

Last edit: 2014-10-09 09:16:09
Jacob Plachta: 2014-10-14 10:25:23

Coordinates are non-negative, not strictly positive. Also, can you check that the data's fine?

Added by:Ajharul Islam Barid
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)