##문제 : [[problem:AUTOPRODUCTION]]

##코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool decision(int x);
int optimise();
bool comp(const int temp1, const int temp2);

int n;  //재료의 가짓수
int r[10], c[10];   //필요한 재료 i의 수, 재료i의 칸수
vector<int> ingredient[10]; //각 칸에 해당하는 재료의 갯수

int main() {
    int cases;

    cin >> cases;
    while (cases--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> r[i] >> c[i];
            ingredient[i].resize(c[i]);
            for (int j = 0; j < c[i]; ++j)
                cin >> ingredient[i][j];
        }
        for (int i = 0; i < n; ++i)
            sort(ingredient[i].begin(), ingredient[i].end(), comp);
        cout << optimise() << endl;
        for (int i = 0; i < 10; ++i)
            ingredient[i].clear();
    }
    return 0;
}

bool decision(int x) {
    int remain = 10;
    //재료순회
    for (int i = 0; i < n; ++i) {
        int temp = x * r[i];
        //각 재료당 칸 순회
        for (int j = 0; j < c[i]; ++j) {
            //추가적으로 칸의 선택이 불가
            if (remain <= 0)    return false;
            temp -= ingredient[i][j];
            remain--;
            //필요한 재료 충당
            if (temp <= 0)  break;
        }
        //재료가 부족하다
        if (temp > 0)   return false;
    }
    //모든 재료가 다 충당됨
    return true;
}

int optimise() {
    int lo = 0, hi = 1000;
    int mid;

    for (int iter = 0; iter < 100; ++iter) {
        mid = (lo + hi) / 2;
        if (decision(mid))
            lo = mid;
        else
            hi = mid;
    }
    return lo;
}

bool comp(const int temp1, const int temp2) {
    return temp1 > temp2;
}

##문제 접근
1. 일단 그리디를 이용해서 각 재료가 수납된 칸들을 내림차순으로 정렬 했습니다.
2. 그다음 이분법을 이용해서 답을 도출해냅니다.

##사용된 함수
1. bool decision(int x) : 재료들을 이용해 아이템을 x개 만들수 있으면 true, 없으면 false를 리턴합니다
2. int optimise() : 이분법을 실행하는 함수입니다. lo = 0, hi = 1000 으로 초기화하고 decision(mid)가 true 를 반환하면 lo에 mid를 대입하고 그렇지 않으면 hi에 mid를 대입해서 이 같은 과정을 100번 반복하고 lo를 리턴합니다.