마라톤 대회

면접 대비

시간 제한2초메모리 제한512 MB

요약

1번에서 N번까지의 단순 경로 중 각 도로의 비용 C*(P-T)^2 (P>T일 때)의 합이 예산 K 이하가 되도록 하는 가장 큰 참가자 수 P를 구한다.

난이도: 보통10점 중 7점
유형: 최단 경로, 그래프, 이분 탐색, 힙
정답자: 아직 제출이 없습니다

문제

마라톤 대회가 열린다. 참가자는 미리 정해진 코스를 따라 달려야 하고, 코스는 아직 정해지지 않았다. 대회가 열리는 곳은 $N$ 개의 교차로와 $M$ 개의 양방향 도로로 이루어져 있다. 도로는 두 교차로를 잇는다. 교차로에는 $1$ 번부터 $N$ 번까지, 도로에는 $1$ 번부터 $M$ 번까지 번호가 붙어 있다.

마라톤 코스는 교차로의 나열 $(V_1, V_2, \dots, V_k)$ 로 나타낸다. $k$ 는 코스에 들어가는 교차로의 개수이다. 시작 교차로 $V_1$ 은 항상 $1$ 번 교차로, 마지막 교차로 $V_k$ 는 항상 $N$ 번 교차로여야 한다. 같은 교차로가 두 번 이상 나오면 안 되고, 연속한 두 교차로는 도로로 이어져 있어야 한다.

대회를 열려면 코스에 들어가는 도로를 통제해야 한다. 도로를 통제하는 데 비용을 지불할 수도 있고 지불하지 않을 수도 있다. 각 도로에는 통제 비용 $C$ 와 지불 인원 상한선 $T$ 가 있다. 마라톤에 참가하는 사람의 수를 $P$ 라고 하면, $P \le T$ 인 도로는 비용을 지불하지 않고 통제한다. $P > T$ 인 도로를 통제하는 비용은 $C \times (P-T)^2$ 원이다. 코스의 통제 비용은 코스에 들어가는 도로의 비용을 모두 더한 값이다.

대회 예산 중에서 도로 통제에 지불할 수 있는 금액은 최대 $K$ 원이다. 코스는 참가할 수 있는 사람이 가장 많아지도록 정하려고 한다. 예산 안에서 코스를 적절히 정했을 때 참가할 수 있는 사람 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 교차로의 수 $N$ , 도로의 수 $M$ , 예산 $K$ 가 주어진다. ( $2 \le N \le 100{,}000$ , $N-1 \le M \le 100{,}000$ , $1 \le K \le 10^9$ )

둘째 줄부터 $M$ 개의 줄에 도로의 정보가 한 줄에 하나씩 주어진다. 도로의 정보는 네 정수 $A$ , $B$ , $C$ , $T$ ( $1 \le A < B \le N$ , $1 \le C, T \le 1{,}000$ )로 이루어진다. $A$ 와 $B$ 는 도로가 잇는 두 교차로의 번호이고, $C$ 와 $T$ 는 그 도로를 통제하는 비용을 계산하는 데 쓰는 값이다.

임의의 두 교차로를 잇는 도로는 많아야 한 개이고, 항상 답을 구할 수 있는 경우만 입력으로 주어진다.

출력

예산 안에서 코스를 적절히 정했을 때 참가할 수 있는 사람 수의 최댓값을 첫째 줄에 출력한다.

설명

코스에 도로 두 개가 들어가고 두 도로의 값이 각각 $(C, T) = (5, 1)$ , $(C, T) = (1, 5)$ 라고 하자. 참가자가 3명이면 통제 비용은 $5 \times (3-1)^2 + 0 = 20$ 원이고, 4명이면 $5 \times (4-1)^2 + 0 = 45$ 원이며, 6명이면 $5 \times (6-1)^2 + 1 \times (6-5)^2 = 126$ 원이다. 예산이 25원이면 이 코스로는 3명까지 참가한다.

예제4

예제 1
입력
```
3 3 5
1 2 1 1
1 3 1 1
2 3 1 1
```
예상 출력
```
3
```
예제 2
입력
```
3 3 3
1 2 1 1
1 3 1 1
2 3 1 1
```
예상 출력
```
2
```
예제 3
입력
```
3 2 25
1 2 5 1
2 3 1 5
```
예상 출력
```
3
```

예제 4

입력

예상 출력