给定一个有向图G，有点权和边权。

小明背着一个背包，去这个图上挖宝石，每走到一条路上，他会因为好奇而捡起这条路上的某些$S_j$个石头，但其实没有任何价值（然而必须捡）。

当走到一个采矿点时，他可以选择挖或者不挖，如果挖，将会付出$W_i$的背包容量，但会获得$V_i$的价值，否则略过。

小明可以在任何时候停止采矿，给出每条边、每个点的信息，求能得到的最大价值。

本人太蒟，除了搜索还有其他方式解此题吗?qwq