样例文件

题目描述

一共有 N 个方格，依次编号为 1 ~ N。

现在让你往方格中填数，每个方格只能填 0 或 1。

填完后，会有 M 次测试。每次测试给出三个互不相同的整数，假设第 i 次测试给出的三个整数依次为 $a_i, b_i, c_i$, 如果编号为 $a_i, b_i, c_i$ 的三个方格中的数恰好依次为 $1, 0, 0$, 则该次测试可以得到一百分，否则不得分。

最后的总分为每次测试得分之和。

现在你已经提前知道了 M 次测试的数据。问：

（1）如何填数，可以使得在后续的测试中得到的总分最大？你只需要输出可以得到的最大总分。

（2）在可以得到最大总分的前提下，你有多少种填数方案？注：两种方案不同，当前仅当存在一个方格，在两种方案中填的数不同。

输入格式

第一行：两个整数 $N, M$

接下来 $M$ 行，每行三个互不相同的整数 $a_i, b_i, c_i$

输出格式

一行，两个整数，以单个空格隔开，依次表示最大总分和方案数。

输入样例

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

输出样例

300 2

样例解释

如果四个格子依次填 1 0 0 0 则可以得到三百分。

如果四个格子依次填 1 0 0 1 也可以得到三百分。

只有这两种方案可以得到三百分。不存在其他可以得到更多分的方案。

数据范围

• 40% 的数据：$3 ≤ N ≤ 10, M ≤ 10^4$；
• 100% 的数据：$3 ≤ N ≤ 20, 1 ≤ M ≤ 2 × 10^5, 1 ≤ a_i, b_i, c_i ≤ N$ 且两两不同。