시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (하단 참고) 512 MB 31 7 7 33.333%

문제

백준 마라톤 대회가 열린다. 마라톤 대회는 미리 정해진 코스를 따라서 달려야 하며, 아직 코스는 정해지지 않았다. 마라톤 대회가 열리는 곳은 N개의 교차로와 M개의 양방향 도로로 이루어져 있다. 도로는 두 교차로를 연결한다. 교차로는 1번부터 N번까지 번호가 매겨져 있고, 도로도 1번부터 M번까지 번호가 매겨져 있다.

마라톤 코스는 (V1, V2, ..., Vk)로 나타낼 수 있다. 이때, k는 마라톤 코스에 포함되어 있는 교차로의 개수이다. 시작 교차로 V1은 항상 1번 교차로, 마지막 교차로 Vk는 항상 N번 교차로이어야 한다. 같은 교차로가 두 번 이상 등장하면 안되고, 연속하는 교차로는 도로로 연결되어 있어야 한다.

마라톤 대회를 열려면 도로를 통제해야 한다. 도로를 통제하려면 비용을 지불해야 할 수도 있고 지불하지 않을 수도 있다. 각 도로에는 도로 통제 비용 C와 지불 인원 상한선 T가 존재한다. P를 마라톤에 참가하는 사람의 수라고 했을 때, P ≤ T인 경우에는 비용을 지불하지 않고 도로를 통제할 수 있다. P > T인 경우에는 C×(P-T)2원이 도로를 통제하는 비용이다.

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

입력

첫째 줄에 교차로의 수 N, 도로의 수 M, 예산 K가 주어진다. (2 ≤ N ≤ 100,000, N-1 ≤ M ≤ 100,000, 1 ≤ K ≤ 109)

둘째 줄부터 M개의 줄에는 도로의 정보가 주어진다. 도로의 정보는 네 정수 A, B, C, T (1 ≤ A < B ≤ N, 1 ≤ C, T ≤ 1,000) 로 이루어져 있다. A와 B는 도로가 연결하는 두 교차로의 번호, C와 T는 그 도로 통제하는 비용을 계산하는데 쓰이는 값이다. 

임의의 두 교차로를 연결하는 도로의 개수는 최대 1개이고, 항상 정답을 구할 수 있는 경우만 입력으로 주어진다.

출력

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

서브태스크 1 (8점)

  • 2 ≤ N ≤ 1,000
  • N-1 ≤ M ≤ 100,000
  • 1 ≤ K ≤ 1,000

서브태스크 2 (14점)

  • 2 ≤ N ≤ 1,000
  • N-1 ≤ M ≤ 100,000
  • 1 ≤ K ≤ 109

서브태스크 3 (12점)

  • 2 ≤ N ≤ 100,000
  • N-1 ≤ M ≤ 100,000
  • 1 ≤ K ≤ 109

예제 입력 1

3 3 5
1 2 1 1
1 3 1 1
2 3 1 1

예제 출력 1

3

예제 입력 2

3 3 3
1 2 1 1
1 3 1 1
2 3 1 1

예제 출력 2

2

예제 입력 3

3 2 25
1 2 5 1
2 3 1 5

예제 출력 3

3

예제 입력 4

4 5 100
1 2 3 4
1 3 1 2
2 3 2 1
3 4 1 1
2 4 1 5

예제 출력 4

9

힌트

예제 1의 경우에 마라톤 코스를 (1, 3)으로 정하면, 3명의 사람이 참가할 수 있게 된다. 이때, 1과 3을 연결하는 도로를 통제하는 비용은 1×(3-1)2 = 4 이다. 4명이 참가하는 경우에는 통제하는 비용이 1×(4-1)2 = 9가 되어서 예산을 초과하게 된다.

예제 2는 예제 1과 같은 경우이지만, 예산이 3원으로 줄어들었다. 따라서, 3명의 사람이 참가할 수 없다. 이때, 2명이 참가하는 경우 통제 비용은 1×(2-1)2 = 1이다.

예제 3의 경우에는 1번 교차로에서 시작해서 3번 교차로에서 끝나는 마라톤 코스는 (1, 2, 3)밖에 없다. 참가하는 사람의 수와 통제 비용을 계산해보면 아래와 같다.

  • 1명 참가: 5×(1-1)2 + 0 = 0
  • 2명 참가: 5×(2-1)2 + 0 = 5 + 0 = 5
  • 3명 참가: 5×(3-1)2 + 0 = 20 + 0 = 20
  • 4명 참가: 5×(4-1)2 + 0 = 45 + 0 = 45
  • 5명 참가: 5×(5-1)2 + 0 = 80 + 0 = 80
  • 6명 참가: 5×(6-1)2 + 1×(6-5)2 = 125 + 1 = 126
  • 7명 참가: 5×(7-1)2 + 1×(7-5)2 = 180 + 4= 184

예산 25로는 최대 3명만 참가가 가능하다.

출처

  • 문제의 오타를 찾은 사람: jh05013

시간 제한 안내

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

  • Python 3: 12초
  • PyPy3: 12초
  • Python 2: 12초
  • PyPy2: 12초

채점

  • 예제는 채점하지 않는다.