Подразделы

Другие разделы

Дата и время

20/04/2024 02:54:53

Авторизация

Зарегистрироваться
Восстановить пароль

Тренировка 5

A. Word Ladder B. Bonus Word C. Contest D. Cycling E. Escape F. Settling Salesman Problem G. Space H. Herbert

C. Contest

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

You and your team are participating in a programming contest. After reading all problems, you have estimated for each problem how long it will take you to solve it. Your teammates have done exactly the same. Now you want to divide the problems, so that the total number of solved problems will be maximized.

Your team is very organized and each team member always writes down all the details on paper. Therefore the computer never forms a bottleneck. The only constraint is that for each team member, the total time required to solve the problems assigned to him should not exceed the time left in the contest.

Input

On the first line an integer `t` (`1\ ≤\ t\ ≤\ 100`): the number of test cases. Then for each test case:

One line with two integers `n` (`1\ ≤\ n\ ≤\ 10`) and `m` (`1\ ≤\ m\ ≤\ 300`). The number of problems and the number of minutes left in the contest.
Three lines with n integers each. Each line describes the solving times for a different team member. The `j`th integer on the `i`th line is denoted by `s_{ij}` : either the time in minutes it takes the `i`th person to solve the `j`th problem (`1\ ≤\ s_{ij}\ ≤\ 300`), or `-1` if the person cannot solve this problem.

Output

For each test case:

One line with the maximum number of problems your team can solve.

Sample input

1
10 300
10 60 -1 -1 10 10 10 240 1 30
15 -1 30 -1 60 60 60 300 5 250
20 -1 -1 60 60 90 90 300 2 245

Sample output

Source: BAPC preliminary contest, 2007