Sleazy Bob 偶然发现了一台自动售货机。在观察了足够多的人购买美味零食后，Bob 意识到这台自动售货机坏了！

Sleazy Bob 观察到以下情况：

1. 有人尝试购买零食。
2. 自动售货机检查该零食是否还有剩余。
3. 如果有剩余，机器会向此人收取该零食的费用。
4. 如果机器成功扣费，它会给此人提供一种不同的零食！如果机器中该种零食已售罄，则可能什么都不给！

Sleazy Bob 注意到，尽管机器坏了，但它至少是一致的。每当顾客从位置 $i$ 购买零食时，机器都会从位置 $f(i)$ 出货，其中 $f$ 是某种可预测的函数。

现在，Bob 想从这台机器中获利。他想从机器中购买一些零食，然后转手以该零食的市场价格卖出。这可能与售货机的售价不同。如果位置 $i$ 的零食很便宜，而位置 $f(i)$ 的零食很贵，他就能大赚一笔！假设 Bob 总能为他的零食找到买家，那么通过购买一定数量（可能为零）的零食并转手卖出，Bob 能获得的最大净收益是多少？你可以假设 Bob 有足够的资金（来自其他非法活动）来支付从自动售货机购买任意数量零食的费用。

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个输入以一个整数 $n$ ($1 \le n \le 100\,000$) 开头，表示机器中零食的位置数量。接下来的 $n$ 行，每行包含 4 个空格分隔的整数 $f, p, m, s$，按位置从 $1$ 到 $n$ 的顺序描述了机器中的零食位置，其中：

• $f$ ($1 \le f \le n$) 是 $f(i)$ 的值。也就是说，这是 Bob 从该位置购买时，机器实际出货的位置。
• $p$ ($1 \le p \le 1\,000\,000$) 是 Bob 从该位置购买时必须支付的价格。
• $m$ ($1 \le m \le 1\,000\,000$) 是该位置零食的市场价格。
• $s$ ($1 \le s \le 1\,000\,000$) 是该位置零食的数量。

输出格式

输出一行，包含一个整数，表示 Sleazy Bob 通过非法利用这台坏掉的自动售货机所能获得的最大利润。

样例

样例输入 1

3
1 2 3 1
2 3 4 1
3 4 5 1

样例输出 1

3

样例输入 2

3
2 2 3 8
3 1 5 6
1 9 4 7

样例输出 2

39

样例输入 3

5
5 9 2 2
1 1 7 4
2 3 6 3
2 2 9 6
1 4 5 1

样例输出 3

22