被暴力包菜了，然而还不会卡……
有一个很暴力的DP：设(f_i)表示给(1)到(i)分好组最多可以分多少组，转移枚举最后一个组。接下来考虑优化这个暴力。
考虑：对于每一个位置(i)，设(pre_i)表示在仅考虑(d)的条件下右端点为(i)的所有满足条件的区间中最左的左端点的前一个位置。显然(pre_i)随(i)的增大是不降的，而右端点为(i)的合法区间的左端点范围恰好为([pre_i + 1 , i])。
这里我们消除了(d)的条件的限制，那么只需要考虑(c)，而一个区间的(c)的限制只取决于其最大值，所以考虑最大值分治。
设正在解决区间([l,r])，我们找到([l+1,r])的最大值(p)（注意是([l+1,r])，因为(f_l)贡献到(f_r)时只考虑(c_{[l+1,r]})的值），那么(forall i in [l,p) , j in [p,r] , maxlimits_{k in [i+1,j]} {c_k} = c_p)。先递归([l,p-1])，然后将([l,p-1])对([p,r])的贡献处理，然后解决([p,r])。
对于([l,p-1])对([p,r])的贡献，注意到(pre_i)不降，所以对于每一个(i in [p,r])，将转移分为三种情况：
①(pre_i leq l , i - c_p < p - 1)，在这种情况下(i)位置会从一段前缀转移过来，而且(i)增加(1)，前缀长度增加(1)。在第一次的时候用线段树查一下最前面一段的最大值，之后每一次(O(1))地更新这个前缀的值。
②(pre_i leq l , i - c_p geq p - 1)，这种情况转移一定会是整个左区间。二分出满足(pre_j leq l)的最大的(j)然后在线段树上区间修改。
③(pre_i > l)，这种情况暴力在线段树上查对应区间。
④(pre_i geq p)，直接退出。
考虑复杂度：①中每一次只有一个(log)的查询和(min(p - l , r - p + 1))地查询，复杂度和最大值分治一致；②每一次只会有一个(log)的修改；③因为对于任意一个(i)，(pre_i)在当前分治区域的左区间、(i)在当前分治区域的右区间的分治区域数量至多为(1)，所以总复杂度是(O(nlogn))。所以总共复杂度为(O(nlogn))。
一些细节：
1、卡空间……求(c)的最大值用线段树而不是ST表；
2、线段树区间打标记并不需要动态维护当前区间的最大(c)值和方案数，只需要在分治区域大小为(1)的时候在线段树上求一下这个位置的实际答案。
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
}
const int MAXN = 1e6 + 1 , MOD = 1e9 + 7;
int add(int a , int b){return a + b >= MOD ? a + b - MOD : a + b;}
struct PII{
int st , nd;
PII(int _st = 0 , int _nd = 0) : st(_st) , nd(_nd){}
}dp[MAXN];
int C[MAXN] , D[MAXN] , pre[MAXN] , N;
//int ST[20][MAXN] , logg2[MAXN];
PII merge(PII a , PII b){
if(a.st == b.st) return PII(a.st , add(a.nd , b.nd));
return a.st > b.st ? a : b;
}
int cmp(int a , int b){return C[a] > C[b] ? a : b;}
namespace segTree2{
int Max[MAXN << 2];
#define mid ((l + r) >> 1)
#define lch (x << 1)
#define rch (x << 1 | 1)
void init(int x , int l , int r){
if(l == r) Max[x] = l;
else{
init(lch , l , mid); init(rch , mid + 1 , r);
Max[x] = cmp(Max[lch] , Max[rch]);
}
}
int query(int x , int l , int r , int L , int R){
if(l >= L && r <= R) return Max[x];
int cur = 0;
if(mid >= L) cur = query(lch , l , mid , L , R);
if(mid < R) cur = cmp(cur , query(rch , mid + 1 , r , L , R));
return cur;
}
}
namespace segTree{
struct node{
PII maxN , mrk;
node(){maxN = mrk = PII(-1e9 , 0);}
}Tree[MAXN * 2 + 100000];
#define mid ((l + r) >> 1)
#define lch (x << 1)
#define rch (x << 1 | 1)
void pushup(int x){Tree[x].maxN = merge(Tree[lch].maxN , Tree[rch].maxN);}
void mark(int x , PII mrk){Tree[x].mrk = merge(Tree[x].mrk , mrk);}
void pushdown(int x){
mark(lch , Tree[x].mrk); mark(rch , Tree[x].mrk);
Tree[x].mrk = PII(-1e9 , 0);
}
void modify(int x , int l , int r , int L , int R , PII mrk){
if(l >= L && r <= R) return mark(x , mrk);
pushdown(x);
if(mid >= L) modify(lch , l , mid , L , R , mrk);
if(mid < R) modify(rch , mid + 1 , r , L , R , mrk);
}
void update(int tar){
int x = 1 , l = 0 , r = N;
while(l != r){
pushdown(x);
if(mid >= tar){x = lch; r = mid;}
else{x = rch; l = mid + 1;}
}
dp[tar] = Tree[x].maxN = merge(dp[tar] , Tree[x].mrk);
while(x >>= 1) pushup(x);
}
PII query(int x , int l , int r , int L , int R){
if(L > R) return PII(-1e9 , 0);
if(l >= L && r <= R) return Tree[x].maxN;
pushdown(x);
PII sum(-1e9 , 0);
if(mid >= L) sum = merge(sum , query(lch , l , mid , L , R));
if(mid < R) sum = merge(sum , query(rch , mid + 1 , r , L , R));
return sum;
}
}
priority_queue < int , vector < int > , greater < int > > q1 , q2;
void maintain(){while(!q2.empty() && q1.top() == q2.top()){q1.pop(); q2.pop();}}
void init(){
/*for(int i = 2 ; i <= N ; ++i)
logg2[i] = logg2[i >> 1] + 1;
for(int i = 1 ; i <= N ; ++i)
ST[0][i] = i;
for(int i = 1 ; 1 << i <= N ; ++i)
for(int j = 1 ; j + (1 << i) - 1 <= N ; ++j)
ST[i][j] = cmp(ST[i - 1][j] , ST[i - 1][j + (1 << (i - 1))]);*/
segTree2::init(1 , 1 , N);
for(int i = 1 ; i <= N ; ++i){
pre[i] = pre[i - 1];
q1.push(D[i]); maintain();
while(q1.top() < i - pre[i]){
q2.push(D[++pre[i]]); maintain();
}
}
}
int qST(int x , int y){
//int t = logg2[y - x + 1];
//return cmp(ST[t][x] , ST[t][y - (1 << t) + 1]);
return segTree2::query(1 , 1 , N , x , y);
}
void solve(int l , int r){
if(l == r)
return segTree::update(l);
int p = qST(l + 1 , r); solve(l , p - 1);
int pos = max(p , l + C[p]);
PII cur = segTree::query(1 , 0 , N , l , pos - C[p] - 1);
while(pos <= r && pre[pos] <= l && pos - C[p] < p){
cur = merge(cur , dp[pos - C[p]]);
dp[pos] = merge(dp[pos] , PII(cur.st + 1 , cur.nd));
++pos;
}
if(pos <= r && pre[pos] <= l){
int L = pos , R = r;
while(L < R){
int Mid = (L + R + 1) >> 1;
pre[Mid] <= l ? L = Mid : R = Mid - 1;
}
segTree::modify(1 , 0 , N , pos , L , PII(cur.st + 1 , cur.nd));
pos = L + 1;
}
while(pos <= r && pre[pos] < p){
cur = segTree::query(1 , 0 , N , pre[pos] , min(pos - C[p] , p - 1));
dp[pos] = merge(dp[pos] , PII(cur.st + 1 , cur.nd));
++pos;
}
solve(p , r);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
N = read();
fill(dp + 1 , dp + N + 1 , PII(-1e9 , 0)); dp[0].nd = 1;
for(int i = 1 ; i <= N ; ++i){C[i] = read(); D[i] = read();}
init(); solve(0 , N);
if(dp[N].st <= 0)
puts("NIE");
else
printf("%d %d
" , dp[N].st , dp[N].nd);
return 0;
}