#include <bits/stdc++.h>
#define PII pair<int, int>

using namespace std;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (! isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

int n;
const int maxn = 5e5 + 10;

bool vis[maxn], p[maxn], now[maxn];
long long dis[maxn];
int l[maxn], r[maxn];

priority_queue<PII, vector<PII>, greater<PII > > q;

int h[maxn], nxt[maxn], en;

struct Edge { int u, v; long long w; } e[maxn * 13];

void addEdge(int u ,int v, long long w) {
	e[++ en] = Edge{u, v, w};
	nxt[en] = h[u];
	h[u] = en;
}

void dij(int k) {
	
	for (int i = 0; i < l[k]; i ++) {		
		dis[i] = 1e18;
		vis[i] = 0;
	}
	dis[0] = 0;
	
	q.push({0, 0});
	while (!q.empty()) {
		int u = q.top().second; 
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = h[u]; i > 0; i = nxt[i]) {
			int v = e[i].v;
			int w = e[i].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
}

signed main() {
	n = read();
	
	for (int i = 1; i <= n; i ++) {
		l[i] = read(), r[i] = read();
		en = 0;
		for (int j = 0; j < l[i]; j ++) nxt[j] = h[j] = 0;
		for (int j = 0; j < l[i]; j ++)
			for (int k = l[i] + 1; k <= r[i]; k ++)
				addEdge(j, (j + k) % l[i], k);
		dij(i);
		
		for (int j = 0; j < l[i]; j ++)
			for (int k = dis[j] - l[i]; k >= 0; k -= l[i])
				now[k] |= 1;
		
		for (int j = 1; j < maxn; j ++)
			if (j == 1) p[j] = now[j];
			else p[j] |= now[j];
	}
	
	int sum = 0;
	for (int i = 1; i < maxn; i ++) sum += p[i];
	cout << (int)(1e9 - sum);
} 

$\text{Input}$

10
4 4
22558 22564
17994 18002
6 6
27820 27821
1011 1012
14109 14116
28551 28558
15707 15723
10402 10424

题目无