34562번 - 터치 앤 리턴

문제

용준이는 터치 앤 리턴이라는 게임을 하기로 했습니다.

게임의 규칙은 다음과 같습니다.

1. 체력을 소모하여 현재 있는 지점에서 통로로 연결된 다른 지점으로 이동할 수 있습니다. 단, 현재 갖고 있는 체력보다 통로의 체력 소모량이 더 큰 경우 이동할 수 없습니다.
2. 매 턴 용준이는 1ドル$번 지점에서 출발하여 원하는 만큼 지점을 방문한 뒤, 다시 1ドル$번 지점으로 돌아와야 합니다. 한 턴 내에서 같은 지점을 중복하여 방문할 수 있습니다.
3. 1ドル$번 지점에 돌아오면, 무조건 $($이번 턴에 방문한 서로 다른 지점의 수 $- 1)^2$ 로 계산된 점수를 획득하고, 한 턴이 종료됩니다.
4. 체력이 0ドル$ 미만이 되는 순간, 게임이 종료됩니다. 즉, 체력이 부족하여 원점에 돌아오지 못한 경우, 점수를 획득할 수 없습니다.

예를 들어, 경로가 1ドル → 2 → 3 → 4 → 3 → 5 → 3 → 2 → 1$ 이라면, 방문한 지점은 ${1,2,3,4,5}$이고, 1ドル$번 지점을 제외하면 4ドル$개의 지점이므로 획득하는 점수는 4ドル^2 = 16$점이 됩니다.

지점의 이름은 1ドル$부터 $N$까지의 정수이며, 지점 간 이동에는 체력이 소모됩니다. 그리고, 주어진 체력 $K$ 이내에서, 이러한 경로 탐색을 여러 번 할 수 있습니다.

목표는 주어진 체력으로 얻을 수 있는 최대 점수를 구하는 것입니다. 이때, 모든 체력을 사용할 필요는 없습니다.

입력

첫째 줄에 지점의 수 $N,ドル 두 지점을 잇는 통로의 수 $M,ドル 용준이의 체력 $K$가 주어집니다. (2ドル \leq N \leq 20; 1 \leq M \leq 300,000円; 1 \leq K \leq 100,000円;$ $N,ドル $M,ドル $K$는 정수)

다음 $M$개 줄에 $a$ $b$ $c$가 주어지는데, 이는 지점 $a$와 지점 $b$ 사이의 통로를 이용할 경우 소모되는 체력이 정수 $c$인 통로를 나타냅니다. 이 통로에서는 양방향 통행이 가능합니다. (1ドル \leq a, b \leq N; a \neq b; 1 \leq c \leq 100,000円$)

출력

주어진 체력으로 얻을 수 있는 최대 점수를 출력해 주세요.

제한

노트