a117. TOI 2023/12 潛力組：材料成本

題目描述

有 N 種材料，編號為 1 到 N。生產一單位材料 i 需要支付加工費 Pi，並消耗 Mi 種其他材料：對其中每種原料 Si,j，需要 Ai,j 單位。

一單位材料的成本，是它使用的全部原料成本加上加工費。若某材料不需要其他原料，它的單位成本就是加工費。原料依賴關係不會形成循環。請算出每種材料的單位成本。

輸入格式

第一行輸入 N，1 ≤ N ≤ 1000。 第二行輸入 N 個加工費 P1 到 PN，1 ≤ Pi ≤ 10。 接著依材料編號輸入 N 組資料。第 i 組先輸入 Mi，0 ≤ Mi ≤ N−1，再輸入 Mi 行，每行為 Si,j、Ai,j，表示需要 Ai,j 單位的材料 Si,j。 1 ≤ Si,j ≤ N，Si,j ≠ i，1 ≤ Ai,j ≤ 10；同一材料的原料種類彼此不同。依賴關係保證沒有循環，所有答案均不超過 2000000000。

輸出格式

輸出 N 行，第 i 行為材料 i 的單位成本。

來源

TOI 2023 年 12 月潛力組〈材料成本〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202312/Cost.pdf