H. Divide

H. Divide

测试数据来自 nnu_contest/1313

H. Divide

时间限制:2s

空间限制:256MB

本题分数:400

题目描述

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

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

输入格式

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

第二行包含 nn 个正整数,分别表示 nn 种石头的重量。

接下来 nn 行,每行包含两个正整数 li,ril_i,r_i ,表示第 ii 种石头能被装入背包的范围。

输出格式

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

样例输入

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

样例输出

样例解释

第一种石头切分成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)

数据范围及限制

测试点编号 nn 1L,R1\le L,R\le 0ai0\le a_i\le 1liri1\le l_i\le r_i\le 测试点分值
1 10 100 100 10 每个测试点40分
2~3 100 10410^4 10410^4 100 每个测试点40分
4~5 1000 10610^6 10610^6 1000 每个测试点40分
6~7 10410^4 10910^9 10910^9 10910^9 每个测试点40分
8~10 10510^5 10910^9 10910^9 10910^9 每个测试点40分

信息

ID
3040
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者