#include <iostream> #include <vector> #include <climits> using namespace std; const int MAXN = 105; int n, m, W; int weights[MAXN], values[MAXN]; vector<pair<int, int>> graph[MAXN]; int dp[MAXN][MAXN]; int energy[MAXN][MAXN]; // 初始化数组 void init() { for (int i = 0; i < MAXN; ++i) { for (int j = 0; j < MAXN; ++j) { dp[i][j] = -1; energy[i][j] = INT_MAX; } } dp[1][weights[1]] = values[1]; energy[1][weights[1]] = 0; } // 动态规划求解 void solve() { for (int u = 1; u <= n; ++u) { for (int w = 0; w <= W; ++w) { if (dp[u][w] == -1) continue; for (const auto& edge : graph[u]) { int v = edge.first; int dist = edge.second; int newWeight = w + weights[v]; if (newWeight <= W && v >= 1 && v <= n) { int newValue = dp[u][w] + values[v]; int newEnergy = energy[u][w] + w * dist; if (dp[v][newWeight] < newValue || (dp[v][newWeight] == newValue && energy[v][newWeight] > newEnergy)) { dp[v][newWeight] = newValue; energy[v][newWeight] = newEnergy; } } } } } } // 找到最大价值和最小体力消耗 pair<int, int> findResult() { int maxValue = -1; int minEnergy = INT_MAX; for (int w = 0; w <= W; ++w) { if (dp[n][w] > maxValue) { maxValue = dp[n][w]; minEnergy = energy[n][w]; } else if (dp[n][w] == maxValue) { minEnergy = min(minEnergy, energy[n][w]); } } return {maxValue, minEnergy}; } int main() { // 读取输入并进行严格检查 if (!(cin >> n >> m >> W) || n < 1 || n >= MAXN || W < 0 || W >= MAXN) { cerr << "输入格式错误或 n、W 超出范围" << endl; return 1; } for (int i = 1; i <= n; ++i) { if (!(cin >> weights[i] >> values[i]) || weights[i] < 0 || values[i] < 0) { cerr << "输入格式错误或第 " << i << " 个城市的物品重量或价值为负数" << endl; return 1; } } for (int i = 0; i < m; ++i) { int x, y, z; if (!(cin >> x >> y >> z) || x < 1 || x > n || y < 1 || y > n || z < 0) { cerr << "输入格式错误或第 " << i << " 条边的信息超出范围" << endl; return 1; } graph[x].emplace_back(y, z); } init(); solve(); auto result = findResult(); cout << result.first << " " << result.second << endl; return 0; }