#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M >> K;
	vector<vector<long double>>dp(N, vector<long double>(K + 1, -MOD));
	dp[0][0] = 0;
	vector<vector<int>>length(N, vector<int>(N));
	vector<vector<int>>gain(N, vector<int>(N));
	for (int i = 0; i < M; i++) {
		cin >> L >> R >> H >> W;
		L--, R--;
		length[L][R] = H;
		length[R][L] = H;
		gain[R][L] = W;
		gain[L][R] = W;
	}
	vector<long double>stay(N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (length[i][j]) {
				stay[i] = max(stay[i], (long double)1 * gain[i][j] / length[i][j]);
			}
		}
	}
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < N; j++) {
			dp[j][i + 1] = max(dp[j][i + 1], dp[j][i] + stay[j]);
			for (int k = 0; k < N; k++) {
				if (length[j][k] && i + length[j][k] <= K) {
					dp[k][i + length[j][k]] = max(dp[k][i + length[j][k]], dp[j][i] + gain[j][k]);
				}
			}
		}
	}
	cout << setprecision(20) << dp[0].back() << endl;
}

### Prompt

Construct a cpp code solution to the problem outlined:

Example

Input

3 3 4
1 2 1 1
2 3 2 4
3 1 1 1


Output

6

### Response

```cpp
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M >> K;
	vector<vector<long double>>dp(N, vector<long double>(K + 1, -MOD));
	dp[0][0] = 0;
	vector<vector<int>>length(N, vector<int>(N));
	vector<vector<int>>gain(N, vector<int>(N));
	for (int i = 0; i < M; i++) {
		cin >> L >> R >> H >> W;
		L--, R--;
		length[L][R] = H;
		length[R][L] = H;
		gain[R][L] = W;
		gain[L][R] = W;
	}
	vector<long double>stay(N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (length[i][j]) {
				stay[i] = max(stay[i], (long double)1 * gain[i][j] / length[i][j]);
			}
		}
	}
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < N; j++) {
			dp[j][i + 1] = max(dp[j][i + 1], dp[j][i] + stay[j]);
			for (int k = 0; k < N; k++) {
				if (length[j][k] && i + length[j][k] <= K) {
					dp[k][i + length[j][k]] = max(dp[k][i + length[j][k]], dp[j][i] + gain[j][k]);
				}
			}
		}
	}
	cout << setprecision(20) << dp[0].back() << endl;
}

```