题目内容

给定一组函数之间的调用关系。每条调用关系用一个有序三元组 $(u, v, w)$ 描述，表示函数 $u$ 调用函数 $v$，并且本次调用需要额外开辟 $w$ 字节的栈空间。

从某个函数出发，沿着调用关系可以形成一条调用链。调用链的总栈内存定义为链上所有调用关系对应的 $w$ 之和；调用链的长度定义为链上出现的函数个数。

请计算两个值：

1. 所有调用链中总栈内存的最大值；
2. 在总栈内存达到上述最大值的前提下，调用链长度的最大值。

如果调用关系构成有向环，即出现递归，则无法定义有限长度的调用链，此时应输出 -1。

约束条件：

• 函数编号 id 的取值范围为 $0 \le id \le 999$。
• 每次调用所需栈内存 size 的取值范围为 $8 \le size \le 10240$。
• 调用关系的总条数不超过 1000。

输入描述

第一行包含一个整数 m，表示调用关系的条数。

接下来 m 行，每行包含三个整数 u、v、w，表示函数 u 调用函数 v，本次调用需要开辟 w 字节的栈空间。

输出描述

如果函数调用关系中存在环，输出 -1。

否则，输出两个以空格分隔的整数：第一个整数表示所有调用链中总栈内存的最大值，第二个整数表示在取得该最大总栈内存时调用链的最大函数个数。

样例1

输入

5
0 1 12
1 2 16
0 3 8
3 4 8
4 2 12

输出

28 4

说明

该调用关系形成有向无环图。

从函数 0 出发可以到达函数 2 的两条调用链分别为：

• $0 \to 1 \to 2$，总栈内存为 $12+16=28$ 字节，包含 3 个函数；
• $0 \to 3 \to 4 \to 2$，总栈内存为 $8+8+12=28$ 字节，包含 4 个函数。

其他调用链的总栈内存都不超过 28 字节。两条链的总栈内存都达到最大值 28 字节，此时选择函数个数最多的链，因此长度为 4。

输出为 28 4。

样例2

输入

1
7 999 10240

输出

10240 2

说明

只有 1 条调用关系，即 $7 \to 999$，它需要 10240 字节栈空间。

图中没有环，唯一调用链包含 2 个函数，所以最大总栈内存为 10240 字节，最大函数个数为 2。

输出为 10240 2。

样例3

输入

1
5 5 32

输出

-1

说明

函数 5 调用自身，形成自环 $5 \to 5$。

由于存在有向环，无法定义有限长度的调用链，因此输出 -1。