교역의 즐거움

아폴리안카와 뷰델스도르프는 최근 접촉하게 된 두 작은 신석기 마을이다. 자원은 $1$부터 $N$까지 번호가 매겨진 $N$종이 있고, 각 마을은 이 중 어떤 자원이든 독립적으로 생산할 수 있지만 효율은 서로 다르다. 자원 $i$ 한 단위를 생산하는 데 아폴리안카는 $A_i$ 인시가 들고, 뷰델스도르프는 $B_i$ 인시가 든다. 현재 아폴리안카는 매 기간 자원 $i$를 $U_i$ 단위씩 생산하고, 뷰델스도르프는 $W_i$ 단위씩 생산한다. 두 마을은 이미 최대 능력으로 일하고 있어서, 지금 투입하는 인시보다 더 많은 인시를 일에 쓸 수 없다. 하지만 교역 덕분에 두 마을은 필요한 자원을 모두 생산하면서도 총 작업 인시를 줄일 수 있고, 남은 시간을 휴식과 게임에 쓸 수 있다. 필요한 것은 두 마을이 협력해 작업을 조율하고 자원을 맞바꾸는 것뿐이다.

예를 들어 $N = 2$이고, 자원 1은 목재, 자원 2는 식량이라고 하자. $A_1 = 1$, $U_1 = 2$, $B_1 = 4$, $W_1 = 1$, $A_2 = 2$, $U_2 = 1$, $B_2 = 3$, $W_2 = 4$이다. 아폴리안카는 4인시를 쓴다. 목재 2단위에 $A_1 U_1 = 2$, 식량 1단위에 $A_2 U_2 = 2$를 쓴다. 뷰델스도르프는 16인시를 쓴다. 목재 1단위에 $B_1 W_1 = 4$, 식량 4단위에 $B_2 W_2 = 12$를 쓴다. 총 생산량은 목재 3단위와 식량 5단위이며, 20인시가 든다.

더 나은 배분이 가능하다. 아폴리안카는 목재 3단위와 식량 0.5단위를 생산하고, 뷰델스도르프는 목재 없이 식량 4.5단위를 생산한다. 총 생산량은 같지만 필요한 작업량은 $3A_1 + 0.5A_2 + 0B_1 + 4.5B_2 = 3 + 1 + 13.5 = 17.5$인시로 줄어든다.

$N = 3$인 다른 예시에서는 $A_1 = 1$, $B_1 = 2$, $A_2 = 2$, $B_2 = 1$, $A_3 = 1$, $B_3 = 1$이고, $i = 1, 2, 3$에 대해 $U_i = W_i = 1$이다. 각 마을은 4인시로 일하고 있다. 작업을 약간 재배치하면, 같은 총 자원을 생산하면서 각 마을이 3인시만 일하면 된다. 아폴리안카는 자원 2를 한 단위 덜 만들고 자원 1을 한 단위 더 만들며, 뷰델스도르프는 그 반대로 한다.

이 값들이 주어졌을 때, 두 마을이 정확히 같은 총 자원을 생산하기 위해 작업해야 하는 총 인시의 최솟값을 구하라. 자원별 인시는 정수일 필요가 없다.

첫 줄에 자원의 개수 $N$ ($1 \le N \le 10^5$)이 주어진다. 각 자원은 $1$부터 $N$까지의 서로 다른 정수로 구분된다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 문제 설명에서 본 것처럼 네 정수 $A_i$, $U_i$, $B_i$, $W_i$ ($1 \le A_i, U_i, B_i, W_i \le 1000$, $i = 1, 2, \dots, N$)가 주어진다.

자원을 생산하는 데 필요한 총 인시의 최솟값을 한 줄에 출력한다. 출력값의 절대 오차 또는 상대 오차는 $10^{-9}$ 이하여야 한다.