题目描述

You are waiting in a long line to get a haircut at a trendy barber shop. The shop has $B$ barbers on duty, and they are numbered $1$ through $B$. It always takes the $k$th barber exactly $M_k$ minutes to cut a customer's hair, and a barber can only cut one customer's hair at a time. Once a barber finishes cutting hair, he is immediately free to help another customer.

While the shop is open, the customer at the head of the queue always goes to the lowest-numbered barber who is available. When no barber is available, that customer waits until at least one becomes available.

You are the $N$-th person in line, and the shop has just opened. Which barber will cut your hair?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow; each consists of two lines. The first contains two space-separated integers $B$ and $N$ -- the number of barbers and your place in line. The customer at the head of the line is number $1$, the next one is number $2$, and so on. The second line contains $M_1$, $M_2$, $\dots$, $M_B$.

输出格式

For each test case, output one line containing "Case #$x$: $y$", where $x$ is the test case number (starting from $1$) and $y$ is the number of the barber who will cut your hair.

3
2 4
10 5
3 12
7 7 7
3 8
4 2 1

Case #1: 1
Case #2: 3
Case #3: 1

提示

Sample Explanation

In Case #1, you are the fourth person in line, and barbers $1$ and $2$ take $10$ and $5$ minutes, respectively, to cut hair. When the shop opens, the first customer immediately has the choice of barbers $1$ and $2$, and she will choose the lowest-numbered barber, $1$. The second customer will immediately be served by barber $2$. The third customer will wait since there are no more free barbers. After $5$ minutes, barber $2$ will finish cutting the second customer's hair, and will serve the third customer. After $10$ minutes, both barbers $1$ and $2$ will finish; you are next in line, and you will have the choice of barbers $1$ and $2$, and will choose $1$.

Limits

• $1 \leq T \leq 100$.
• $1 \leq N \leq 10^9$.

Small dataset(11 Pts)

• Time limit: 240 5 seconds.
• $1 \leq B \leq 5$.
• $1 \leq M_k \leq 25$.

Large dataset

• Time limit: 480 10 seconds.
• $1 \leq B \leq 1000$.
• $1 \leq M_k \leq 100000$.