#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 (auto& edge : graph[u]) { int v = edge.first; int dist = edge.second; int newWeight = w + weights[v]; if (newWeight <= W) { 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 || (dp[n][w] == maxValue && energy[n][w] < minEnergy)) { maxValue = dp[n][w]; minEnergy = energy[n][w]; } } return {maxValue, minEnergy}; } int main() { cin >> n >> m >> W; for (int i = 1; i <= n; ++i) { cin >> weights[i] >> values[i]; } for (int i = 0; i < m; ++i) { int x, y, z; cin >> x >> y >> z; graph[x].emplace_back(y, z); } init(); solve(); auto result = findResult(); cout << result.first << " " << result.second << endl; return 0; }