#P3216. 话旧2

话旧2

话旧2

题目描述

设 nn 为非负整数,函数 ff 在 [0,n][0,n] 上连续,满足 f(0)=f(n)=0f(0)=f(n)=0,且整个区间上的最小值为 00。对每个 0≤i<n0\le i<n 的整数 ii,ff 在 (i,i+1)(i,i+1) 上都是斜率为 11 或 −1-1 的一次函数。所有极值点都在整数位置。

给定 kk 条整点的函数值,求满足条件的函数数目,以及在所有满足条件的函数中,函数最大值最高能达到多少。

输入格式

第一行包含两个整数 n,kn,k(0≤n≤1090\le n\le 10^9,0≤k≤1060\le k\le 10^6)。

接下来 kk 行,每行包含两个整数 xi,f(xi)x_i,f(x_i),表示给定的整点及其函数值。同一个整点可能出现多次。

保证第一问的答案非零。

输出格式

输出一行两个整数。第一个是满足条件的函数数目除以 1994041719940417 的余数,第二个是 f(x)f(x) 能达到的最大值。

6 9
4 2
4 2
2 0
4 2
6 0
5 1
2 0
0 0
0 0
1 2

本题由 jyk 改编自 [ZJOI2013] 话旧。