Description

I got a young body.

~by anonymous coroner

You are a coroner, and you need to buy some Formalin to keep your body in good condition. There're n kinds of Formalin, and you have p dollars. Luckily the Formalin is on sale. If you buy exactly k kinds of Formalin, you only need to pay the most expensive one of them.

You got n products and p dollars.

Everytime you buy exactly k products at once, you only need to pay the most expensive product among the k products.

For the i-th product, the price equals to ai.

Find the maximum number of products you can buy with p dollars.

 

Example:

If n=5 and you got p=6 dollars.

If you buy exactly k=2 products, you only need to pay the most expensive one of them.

Products' price: 2, 4, 3, 5, 7.

In this case, you can buy products of price 4, 3 then you only need to pay 4 dollars.

You left with 2 dollars, then you can buy products of price 2.

The maximum number of products you can buy in this case is 3.

Input

The input start with t(1<= t <=10) means number of testcases.

Each testcase contains two lines.

First line contains three numbers n(2<=n<=3*10^5), p(1<= p <= 10^9), k(2 <= k <= n).

Second line contains n integer ai(1 <= ai <= 10000).

Output

For each testcase print the maximum number of products you can buy with p dollars.

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I shall take no wife, hold no lands, father no children.

~ by anonymous loser.

The night's watch needs to guard The Wall.

But they're lack of resource. They can only choose q-2 men from q men to guard The Wall.

Help them find the maximum number of section they can protect.

There're n sections in a line numbered from 1 to n.

There're q soldiers, for i-th soldier, he can guard from section L_i to R_i(1 <= i <= q)

A section is guarded if at least one soldier guard the section.

You can only hire q-2 soldiers.

You need to find the maximum number of sections that can be guarded by hiring q-2 soldiers from q soldiers.

 

Example

If you got n = 4 sections and q = 3 soldiers.

First soldier guard L_1 = 1, R_1 = 1.

Second soldier guard L_2 = 2, R_2 = 2.

Third soldier guard L_3 = 3, R_3 = 4.

You can hire q-2 = 1 soldier.

The best solution is hired the third soldier then you got 2 section guarded.

The answer will be 2.

Input

The input first contains one integer t( 1 <= t <= 5) which means the number of testcases.

Each testcase first contains two numbers n, q(3 <= n, q <= 5000).

Then the following q lines, each line contains two integer L_i, R_i( 1<= L_i <= R_i <= n )

Output

For each testcase print a integer which means the maximum number of sections that can be guarded by hiring q-2 soldiers.

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the year of 2014, a well-known song has born...... and the name is "My Skate Shoes"(我的滑板鞋). 

The song is known for its brainwashing style. The singer, Joseeh Pummanlon(約瑟翰 ‧ 龐麥郎), just slides left, then slide right... then slide everywhere with his skate shoes, like the step of devil, like the step of devil.

---

Now Pummanlon is at the position 0. He has a sequence of commands which tells him to slide left or to slide right. 'L' is to slide left, 'R' is to slide right.

For example, "LRLR" means he will slide to position -1, then 0, then -1, and stop at position 0.

However, Pummanlon wants to free his sliding style at today's show. He still receives the sliding commands, but he might not perform some of the commands.

For example, if Pummanlon receives the commands "LRLR", then here are some possible outcomes:

• "LRLR": Pummanlon moves to the left, to the right, then to the left again and end up at position -1.
• "LRLR": Pummanlon moves to the left, to the right, then to the left and to the right again and end up at position 0.
• "LRLR": Pummanlon doesn't move, he stands at position 0 like a blockhead instead of devil.
• "LRLR": Pummanlon moves to the left, to the right, then to the right again and end up at position 1.

Pummanlon doesn't know which command will be performed since he will not know the mood while he's performing.Thus, he wants to know how many different positions may Pummanlon stops at.

Input

The first line contains an integer N, indicates the number of commands.

The second line cocntains a string, contains exactly N commands of 'L' and 'R'.

1 <= N <= 10⁵

Output

Print one integer — the number of different positions Pummanlon may end up at.

Remember to print a '\n' at the end of the integer.

---

Take sample as example, Pummanlon may end up anywhere between -2 and 2:

• LL -> -2
• LLR -> -1
• LR -> 0
• R -> 1
• RR -> 2

Sample Input  Download

Sample Output  Download

Tags

Discuss