#include<bits/stdc++.h>
using namespace std;

const int N = 2005;
const int M = 805;

int value[N];                         // 每个节点的价值
vector<pair<int,int>> g[N];           // 邻接表：g[u] 存 (v, w) 表示 u -> v 代价 w

bool visited[N][M];                   // 记忆化标记：状态 (u, cost) 是否已经计算过
long long dis_cost[N][M];             // 记忆化数组：从 u 出发剩余 cost 能获得的最大价值


// DFS + 记忆化
// 返回：从节点 npos 出发，在剩余 cost 的预算下能获得的最大价值
long long dfs(int npos, int cost)
{
    // 如果这个状态已经计算过，直接返回保存的结果
    if(visited[npos][cost]) return dis_cost[npos][cost];

    visited[npos][cost] = true;   // 标记该状态已经访问

    // 至少可以停在当前节点，获得当前节点的价值
    long long ans = value[npos];

    // 遍历所有从 npos 出发的边
    // 使用 const auto& 避免复制 pair，提高性能
    for(const auto &edge : g[npos])
    {
        int v = edge.first;   // 下一节点
        int w = edge.second;  // 边的代价

        // 如果预算足够，可以走这条边
        if(cost >= w)
        {
            // 走这条边后获得的价值
            long long cand = ...