记录编号	132705	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.367 s
提交时间	2014-10-26 15:17:48	内存使用	7.82 MiB

/*=============================================================================================================================*/
/*======================================================Code by Asm.Def========================================================*/
/*=============================================================================================================================*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <memory.h>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <ctime>
#include <iterator>
#include <functional>
#include <cstdlib>
using namespace std;
#define forall(it,v) for(__typeof(v.begin()) it = v.begin();it < v.end();++it) 
#define pb push_back
#define REP(i,j,k) for(i = j;i <= k;++i)
#define REPD(i,j,k) for(i = j;i >= k;--i)
typedef long long LL;
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("qc.in","r");
FILE *out = fopen("qc.out","w");
#endif
template <typename T>
void getint(T &x){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 + c - '0';
}
/*==============================================WORK===========================================================*/
const int maxn = (int)2e5 + 4;

inline void putLL(const LL&x){
	if(x < 1000000000){fprintf(out, "%d\n", x);return;}
	int l = x / 1000000000, r = x % 1000000000;
	fprintf(out, "%d%09d\n", l, r);
}

struct Obj{
	int w, v, loc;
	bool operator < (const Obj &b)const{
		return w > b.w;
	}
}O[maxn] = {{0,0,0}};
int n, m, L[maxn], R[maxn], now = 0, Sumcnt[maxn] = {0};
LL S, SumV[maxn] = {0};
int V[maxn] = {0};//用于计算"价格"前缀和 & 个数前缀和
inline LL f(int W){///////////////////////////////////////////////////
	LL ans = 0; SumV[0] = 0;Sumcnt[0] = 0;
	int i;
	if(O[now].w > W) while(now < n && O[now+1].w >= W)
			++now, V[O[now].loc] = O[now].v;
	else while(now && O[now].w < W)
		V[O[now].loc] = 0, --now;
	for(i = 1;i <= n;++i)
		SumV[i] = SumV[i-1] + V[i], Sumcnt[i] = Sumcnt[i-1] + bool(V[i]);
	for(i = 0;i < m;++i)
		ans += (SumV[R[i]] - SumV[L[i]-1]) * (Sumcnt[R[i]] - Sumcnt[L[i]-1]);
	return ans;
}
int main(){
	int i, j = 0, k;
	LL ans, t, t2;
	int Wcase[maxn] = {0}, Wcnt = 0;
	getint(n), getint(m), getint(S);
	for(i = 1;i <= n;++i){
		getint(O[i].w), getint(O[i].v);
		O[i].loc = i;
	}
	sort(O + 1, O + n + 1);
	O->w = O[1].w + 1;
	for(i = 0;i < m;++i)
		getint(L[i]), getint(R[i]);
	for(i = 1;i <= n;++i)
		if(!Wcnt || O[i].w != Wcase[Wcnt-1])
			Wcase[Wcnt++] = O[i].w;
	i = 0, j = Wcnt-1;
	while(i <= j){
		k = (i + j) >> 1;
		t = f(Wcase[k]);
		if(t == S){ans = 0;break;}
		if(t > S)j = k - 1;
		else i = k + 1;
	}
	ans = S > t ? S - t : t - S;
	t2 = f(Wcase[i ^ j ^ k]);//i ^ j ^ k表示i和j中不等于k的那一个
	t2 = S > t2 ? S - t2 : t2 - S;
	if(t2 < ans)ans = t2;
	putLL(ans);
	//----------------------------------------------------------------------------------------------------------------------
	#if defined DEBUG
	cout << endl << (double)clock() / CLOCKS_PER_SEC <<endl;
	#endif
	return 0;
}
/*=============================================================================================================================*/