H. Divide

时间限制：2s

空间限制：256MB

本题分数：400

题目描述

前段时间，小R她们宿舍一起去爬山了，虽然爬的很累，但是小R爬到山顶的时候就在想，如果这些漂亮的石头能带走就好了，这些石头们仿佛听到了她的心声，赐予了她一种魔法，使得小R可以对这些石头进行分割，但是同时石头也给小R出了一个难题。

石头们告诉小R，山上一共有 \(n\) 种石头，每种石头只有一大块，同时石头们告诉小R，每种石头的重量，它们还给小R提供了若干个魔法背包用来装石头，这些背包有个限制，它们装入的石头的总重量必须在 \([L,R]\) 之间，而且对于第 \(i\) 种石头，能被装入背包的重量必须在 \([l_i,r_i]\) 之间。最后，石头们告诉小R，只要小R能求出最多可以装下多少个魔法背包，就可以带走她喜欢的石头。

输入格式

第一行包含三个正整数 \(n,L,R\) ，分别表示石头的种数，魔法背包的范围。

第二行包含 \(n\) 个正整数，分别表示 \(n\) 种石头的重量。

接下来 \(n\) 行，每行包含两个正整数 \(l_i,r_i\) ，表示第 \(i\) 种石头能被装入背包的范围。

输出格式

一个整数，表示最多可以装下多少个魔法背包。

样例输入

4 10 12
4 20 10 6
1 2
3 5
2 4
0 2

样例输出

4

样例解释

第一种石头切分成4=1+1+1+1，

第二种石头切分成20=5+5+5+5，

第三种石头切分成10=2+2+3+3，

第四种石头切分成6=2+2+1+1。

那么可以装下四个背包，分别是：

（1，5，2，2）（1，5，2，2）（1，5，3，1）（1，5，3，1）

数据范围及限制

测试点编号	\(n\)	\(1\le L,R\le \)	\(0\le a_i\le \)	\(1\le l_i\le r_i\le \)	测试点分值
1	10	100	100	10	每个测试点40分
2~3	100	\(10^4\)	\(10^4\)	100	每个测试点40分
4~5	1000	\(10^6\)	\(10^6\)	1000	每个测试点40分
6~7	\(10^4\)	\(10^9\)	\(10^9\)	\(10^9\)	每个测试点40分
8~10	\(10^5\)	\(10^9\)	\(10^9\)	\(10^9\)	每个测试点40分