#include <iostream> #include <vector> #include <climits> #include <algorithm> using namespace std; const int MAXN = 105; int n, m, W; int w[MAXN], v[MAXN]; vector<pair<int, int>> adj[MAXN]; int dp[MAXN][MAXN]; int cost[MAXN][MAXN]; // 深度优先搜索函数 void dfs (int u, int weight, int value, int c) { if (weight > W) return; if (dp [u][weight] < value || (dp [u][weight] == value && cost [u][weight] > c)) { dp [u][weight] = value; cost [u][weight] = c; for (auto edge : adj [u]) { int vv = edge.first; int dist = edge.second; dfs (vv, weight + w [vv], value + v [vv], c + weight * dist); } } } int main() { cin >> n >> m >> W; for (int i = 1; i <= n; ++i) { cin >> w[i] >> v[i]; } for (int i = 0; i < m; ++i) { int x, y, z; cin >> x >> y >> z; adj[x].emplace_back(y, z); } // 初始化 dp 和 cost 数组 for (int i = 1; i <= n; ++i) { for (int j = 0; j <= W; ++j) { dp [i][j] = -1; cost [i][j] = INT_MAX; } } dp [1][w [1]] = v [1]; cost [1][w [1]] = 0; // 从起点开始搜索 dfs (1, w [1], v [1], 0); int maxValue = -1; int minCost = INT_MAX; for (int i = 0; i <= W; ++i) { if (dp[n][i] > maxValue || (dp[n][i] == maxValue && cost[n][i] < minCost)) { maxValue = dp[n][i]; minCost = cost[n][i]; } } cout << maxValue << " " << minCost << endl; return 0; }