바이러스 폭탄

한 화학자가 원자 바이러스 폭탄을 만들었다. 폭탄은 이렇게 작동한다.

바이러스의 형태는 $N$가지다. 1초마다 한 형태의 바이러스는 같은 형태나 다른 형태의 바이러스 한 마리 이상으로 변이한다. 또 각 형태는 변이하는 그 1초 동안 정해진 개수의 삼중수소 원자를 만든다. 지금까지 만들어진 원자의 총 개수가 임계값 $L$에 도달하면 수소폭탄처럼 폭발한다.

환자가 감염된 순간부터 폭발할 때까지 걸리는 시간을 구한다.

간단한 예로 형태가 하나뿐인 바이러스를 보자. 이 바이러스는 1초마다 같은 형태의 바이러스 두 마리로 변이하고, 그 1초 동안 삼중수소 원자를 하나 만든다. $L = 15$이라고 하자. 1초 후에는 바이러스가 두 마리, 원자가 한 개다. 2초 후에는 바이러스가 네 마리, 원자가 세 개다. 3초 후에는 바이러스가 여덟 마리, 원자가 일곱 개다. 4초 후에 폭탄이 터진다.

조금 더 복잡한 예로 형태가 A와 B 두 가지이고 $L = 500$인 경우를 보자. A 형태의 바이러스는 1초마다 A 형태 세 마리와 B 형태 한 마리로 변이하면서 원자를 한 개 만든다. B 형태의 바이러스는 B 형태 두 마리로 변이하면서 원자를 백 개 만든다. A 형태 한 마리에서 시작하면 1초 후에는 A가 3마리, B가 1마리, 원자가 1개다. 2초 후에는 A가 9마리, B가 5마리, 원자가 104개다. 3초 후에는 A가 27마리, B가 19마리, 원자가 613개다. 따라서 답은 3초다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫째 줄에는 $N$과 $L$이 주어진다. ($1 \le N \le 20$, $1 \le L \le 10^9$)

이어서 $N$개 줄에 각 형태의 설명이 한 줄씩 주어진다. 한 줄에는 $1000$보다 작은 음이 아닌 정수 $N+1$개가 있다. 앞의 $N$개는 그 형태가 각 형태의 바이러스 몇 마리로 변이하는지를 나타내고, 마지막 수는 변이하는 동안 만드는 삼중수소 원자의 개수다.

각 테스트 케이스마다 한 줄씩 출력한다. 환자는 첫 번째 형태의 바이러스 한 마리에 감염된 상태에서 시작한다. 원자는 사라지지 않고 계속 쌓이므로, 누적 개수가 처음으로 $L$ 이상이 되는 순간까지 걸린 시간을 초 단위로 출력한다. 폭탄이 영원히 터지지 않으면 lucky를 출력한다. 답은 32비트 정수의 범위를 넘을 수 있다.