15704번 - 백준 마라톤 대회 서브태스크

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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