혼합 정수 이차 계획법

여러분은 이 문제에서 다음과 같이 변형된 최소 비용 최대 유량 문제를 해결해야 합니다. 변형된 문제에 한하는 조건은 다음과 같습니다.

• 그래프에는 $n$개의 정점과 $m$개의 방향 있는 간선이 있습니다. $1$번 정점이 시작점이며, $n$번 정점이 끝점입니다. 중복 간선이나 자기 자신을 향하는 간선은 없습니다.
• 각 간선에는 정수 세 개의 순서쌍 $(a,b,c)$가 있습니다. 이때 $0 \le a$가 반드시 성립하고, $a \neq 0$인 간선은 최대 $100$개 존재합니다.
• 순서쌍 $(a_i,b_i,c_i)$를 갖는 간선을 통해 최대 $c_i$단위의 자원을 보낼 수 있고, $x$단위의 자원을 보냈을 때 소모되는 비용은 $a_i x^2+b_i x$입니다. 비용이 음수가 될 수 있습니다.
• 각 간선을 통해 보내는 자원의 양은 음이 아닌 정수여야 합니다.

다음은 기본적인 최소 비용 최대 유량 문제에 따른 본 문제의 조건입니다.

• 여러분은 시작점에서 끝점까지 보내는 자원의 양을 최대화하면서, 동시에 요구되는 비용을 최소화해야 합니다.
• 시작점에서 나가는 자원의 양과 끝점으로 들어오는 자원의 양은 같아야 합니다.
• 시작점과 끝점을 제외하고, 모든 정점에 대해 들어오는 자원의 양과 나가는 자원의 양은 같아야 합니다.

문제의 조건에 따른 그래프가 주어졌을 때, 문제를 해결하고 최대 유량과 최소 비용을 출력하는 프로그램을 작성하세요.

첫 번째 줄에 정점의 개수 $n$과 간선의 개수 $m$이 공백으로 분리되어 주어집니다. ($2 \le n \le 200$, $1 \le m \le \min(n(n-1),1500)$)

두 번째 줄부터 $m$개의 줄에 걸쳐 간선에 대한 정보가 주어집니다.

그 중 $i$번째 줄에는 $i$번째 간선에 관한 5개의 정수 $u_i$, $v_i$, $a_i$, $b_i$, $c_i$가 공백으로 분리되어 주어집니다. 이는 순서쌍 $(a_i,b_i,c_i)$를 가지며 $u_i$에서 $v_i$로 향하는 유향 간선을 의미합니다. ($1 \le u,v \le n$, $u \ne v$, $0 \le a_i\le 200$, $-200 \le b_i \le 200$, $1 \le c_i \le 10$)

$a_i \neq 0$인 간선은 최대 $100$개임이 보장됩니다. 또한, 중복 간선이나 자기 자신을 향하는 간선은 없음이 보장됩니다.

한 줄에 두 정수 $f$와 $c$를 공백으로 분리하여 출력합니다. $f$는 그래프의 최대 유량, $c$는 최대 유량에 대응되는 최소 비용입니다. 비용이 음수가 될 수 있음에 유의하세요.