Bob 돕기

Bob은 피자를 매우 좋아하지만 항상 돈이 부족하다. 어느 날 그는 자신이 가장 좋아하는 식당인 Alfredo's Pizza Restaurant가 대회를 연다는 소식을 읽는다. 각 피자를 최대 한 번 살 수 있을 때 얻을 수 있는 단위 넓이당 최저 가격을 가장 먼저 알려 주는 사람에게 큰 피자를 준다는 것이다.

"쉽네!"라고 Bob은 생각한다. "피자마다 가격을 넓이로 나눈 뒤 가장 작은 값을 고르면 되잖아." 하지만 문제는 조금 더 까다롭다. 일부 피자는 다른 피자에 쓸 수 있는 할인 쿠폰을 함께 주며, 이 쿠폰들은 겹쳐서 함께 적용할 수 있다. 피자는 한 번에 하나씩 차례로 사야 하고, 쿠폰은 아직 사지 않은 피자에만 사용할 수 있다. 이미 산 피자에 할인을 소급 적용할 수는 없다.

당신은 비어 있지 않은 어떤 피자 집합을 사고(각각 최대 한 번) 각 피자의 할인된 가격을 지불한다. 이 구매의 단위 넓이당 가격은 지불한 총 가격을 산 피자들의 총 넓이로 나눈 값이다. Bob이 얻을 수 있는 최소 단위 넓이당 가격을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 Alfredo가 제공하는 피자의 수를 나타내는 정수 $m$ ($1 \le m \le 15$)으로 시작한다. 입력은 $m = 0$인 줄로 끝나며, 이 줄은 처리하지 않는다.

그다음 $m$개의 줄이 이어진다. $i$번째 줄($1 \le i \le m$)은 피자 $i$를 설명하며 세 정수 $p_i$, $a_i$, $n_i$로 시작한다. 각각 피자의 가격($1 \le p_i \le 10000$), 넓이($1 \le a_i \le 10000$), 그 피자를 살 때 받는 할인 쿠폰의 수($0 \le n_i < m$)이다. 이어서 $n_i$개의 정수 쌍 $x_{i,j}$와 $y_{i,j}$가 온다. 피자 $i$를 사면 피자 $x_{i,j}$ ($1 \le x_{i,j} \le m$, $x_{i,j} \ne i$)에 대해 $y_{i,j}$ 퍼센트($1 \le y_{i,j} \le 50$)를 할인해 주는 쿠폰을 받는다. 각 $i$에 대해 $x_{i,j}$ 값들은 서로 다르다.

각 테스트 케이스마다 얻을 수 있는 최저 단위 넓이당 가격을 한 줄에 출력한다. 이는 비어 있지 않은 모든 구매 피자 집합과 모든 구매 순서에 대해 (지불한 총 가격) / (산 총 넓이)의 최솟값이다. 이 값을 소수점 아래 넷째 자리까지 반올림하여 출력한다.

쿠폰은 곱셈으로 겹쳐진다. 예를 들어 기본 가격이 10인 피자가 구매 전에 50 퍼센트 쿠폰과 20 퍼센트 쿠폰을 받았다면 $10 \times 0.5 \times 0.8 = 4$만 지불하면 된다.