马上就是小苗的生日了，为了给小苗准备礼物，小葱兴冲冲地来到了商店街。商店街有 个商店，并且它们之间的道路构成了一棵树的形状。
第 个商店只卖第 种物品，小苗对于这种物品的喜爱度是 ，物品的价格为 ，物品的库存是 。但是商店街有一项奇怪的规定：如果在商店 买了东西，并且有一个商店 在 到 的路径上，那么必须要在商店 买东西。小葱身上有 元钱，他想要尽量让小苗开心，所以他希望最大化小苗对买到物品的喜爱度之和。
这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为 OI 选手的你，你能帮帮他吗？
