사우나

사진: SM (cc-by-sa3.0)

핀란드인들은 사우나 이용을 좋아한다. 사실 그리 이상한 일은 아니다. 사우나 목욕은 기분이 좋고 대개 좋은 사람들과 함께하기 때문이다.

하지만 사람들이 함께 모이면 종종 문제가 생긴다. 사우나를 이용할 때 가장 중요한 것은 온도를 올바르게 설정하는 것이다. 핀란드인은 사우나 온도에 매우 까다로울 수 있다. 서로 다른 핀란드인들은 견딜 수 있는 최고 온도가 서로 다르다. 특정 핀란드인에게 온도가 너무 높으면 그 핀란드인은 집으로 돌아간다. 특정 핀란드인이 견딜 수 있는 온도 범위 안에서도 온도에 따라 그 핀란드인의 행복도가 달라진다. 핀란드인의 행복도는 이차 함수($ax^2 + bx + c$ 형태)를 따른다.

많은 핀란드인이 사우나를 이용하고 있으며 여러분의 도움이 필요하다. 사우나 온도를 최적으로 설정했을 때 핀란드인들의 행복도 합의 최댓값을 구할 수 있는가? 온도가 어떤 핀란드인이 견딜 수 있는 수준보다 높게 설정되면 그 핀란드인은 전체 행복도에 아무것도 기여하지 않는다(대신 집으로 돌아갔기 때문이다). 온도는 켈빈 단위로 주어지며, 하한은 $0 \textrm{ K}$이고 상한은 $100\,000 \textrm{ K}$이다.

배점

여러 테스트 케이스 그룹으로 여러분의 풀이를 테스트한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ | $21$ | $N \le 1000$, 모든 $t$가 같다.

$2$ | $29$ | $N \le 1000$, 모든 $a$가 양수이다(즉, 핀란드인들은 극단적인 온도를 좋아한다).

$3$ | $38$ | $N \le 1000$, 모든 $a$가 음수이다.

$4$ | $12$ | 추가 제한이 없다.

첫째 줄에 핀란드인의 수를 나타내는 정수 $1 \le N \le 100\,000$이 주어진다. 그 뒤에 핀란드인마다 한 줄씩, $N$개의 줄이 주어진다. 각 줄에는 네 정수 $a, b, c$와 $t$ ($-10^9 \le a,b,c \le 10^9, 1 \le t \le 100\,000$)가 주어진다. 이는 해당 핀란드인의 행복도 함수가 $ax^2 + bx + c$이고, $0 \textrm{ K}$ 이상 $t\textrm{ K}$ 이하의 온도만 견딜 수 있음을 나타낸다. 이 함수는 $0$와 $t$ 사이의 모든 값에서 양수임이 보장된다.

온도를 올바르게 설정했을 때 달성할 수 있는 가장 큰 행복도를 하나의 수로 출력한다. 정답의 상대 오차 또는 절대 오차가 최대 $10^{-5}$이면 정답으로 인정된다.

이 경우 최적 온도는 $0 \textrm{ K}$이다. 이 경우 두 핀란드인의 행복도는 같다: $1 \cdot 0^2 - 6 \cdot 0 + 10 = 10$. 이들의 행복도 합은 $10 + 10 = 20$이다.

이 경우 최적 온도는 $\frac{10}{3} \textrm{ K}$이다. 첫 번째 핀란드인의 행복도는 $-3(\frac{10}{3})^2 + 20 \cdot \frac{10}{3} + 3 = -\frac{100}{3} + \frac{200}{3} + 3 = 36 + \frac{1}{3}$이다. 이 경우 두 번째 핀란드인은 온도가 너무 높아서 집으로 돌아간다(그녀는 최대 $1\textrm{ K}$의 온도까지만 견딜 수 있다). 따라서 전체 행복도는 $36 + \frac{1}{3}$이다.