A2066. 魔杖
编程题
提高+/省选-
知识点
题目描述
Smart 在春游时意外地得到了一种好东西——一种非常珍贵的树枝。这些树枝可以用来做优质的魔杖！
选择怎样的切割方式来制作魔杖非常重要，关键问题是——一把魔杖既不能太长、又不能太短，且制作出来的魔杖不能有冲突……
Smart 得到的这些树枝在属性上完全相同。每一根树枝都有 $n$ 段（用 $1$~ $n$ 编号），给定了每段的长度 $l$ 和每段的魔力值 $m$ 。你可以做的就是选择一段或连续的几段，把它们作为一个整体切下来，再用来制作魔杖。但是一根魔杖的长度不能太长，不能大于给定的值 $h$；也不能太短，不能小于给定的值 $low$ 。
魔杖有一个奇怪的要求：如果某一根魔杖的制作材料是另一根魔杖的一部分，则这两根魔杖之间将发生冲突。比如说树枝有三段，从左到右的长度分别为 $4$ 、 $1$ 、 $3$ ，Smart需要长度为 $4$ 到 $5$ 之间的魔杖。他可以用一根树枝的前两段做出一个长度为 $5$ 的魔杖，用一根树枝的后两段做出长度为 $4$ 的魔杖；但他决不能用一根树枝的前两段做了魔杖后再单独使用另一根树枝的第一段做成魔杖，因为前者包含了后者的所有成分，这会导致冲突。
我们假设 Smart 可以得到任意多这样的树枝。 Smart 需要制作出若干个互不冲突的魔杖，使所有魔杖的魔力值之和最大。（魔杖的长度就是组成它的那些段的长度的总和，魔力值亦然）。
选择怎样的切割方式来制作魔杖非常重要，关键问题是——一把魔杖既不能太长、又不能太短，且制作出来的魔杖不能有冲突……
Smart 得到的这些树枝在属性上完全相同。每一根树枝都有 $n$ 段（用 $1$~ $n$ 编号），给定了每段的长度 $l$ 和每段的魔力值 $m$ 。你可以做的就是选择一段或连续的几段，把它们作为一个整体切下来，再用来制作魔杖。但是一根魔杖的长度不能太长，不能大于给定的值 $h$；也不能太短，不能小于给定的值 $low$ 。
魔杖有一个奇怪的要求：如果某一根魔杖的制作材料是另一根魔杖的一部分，则这两根魔杖之间将发生冲突。比如说树枝有三段，从左到右的长度分别为 $4$ 、 $1$ 、 $3$ ，Smart需要长度为 $4$ 到 $5$ 之间的魔杖。他可以用一根树枝的前两段做出一个长度为 $5$ 的魔杖，用一根树枝的后两段做出长度为 $4$ 的魔杖；但他决不能用一根树枝的前两段做了魔杖后再单独使用另一根树枝的第一段做成魔杖，因为前者包含了后者的所有成分，这会导致冲突。
我们假设 Smart 可以得到任意多这样的树枝。 Smart 需要制作出若干个互不冲突的魔杖，使所有魔杖的魔力值之和最大。（魔杖的长度就是组成它的那些段的长度的总和，魔力值亦然）。
输入格式
第一行有三个用空格隔开的整数，分别表示 $n$、$low$、$h$。
第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $l_i$ 。
第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $m_i$。
第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $l_i$ 。
第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $m_i$。
输出格式
输出一行一个整数，表示能够获得的魔力值的最大值。
输入输出样例
输入 #1
6 4 5 1 3 3 2 2 1 2 3 1 4 5 2
输出 #1
21
说明/提示
#### 样例输入输出 1 解释
取 $[1$ $3]$ $[3$ $2]$ $[2$ $2$ $1]$ 做成魔杖，得到最大权值 $2+3+1+4+4+5+2=21$ 。
---
#### 数据规模与约定
对于$100\%$的数据，保证：
- $1\le n\le 1000$，$1\le low\le h < 2^{31}$。
- $1 \leq l_i, m_i \le 10^5$
取 $[1$ $3]$ $[3$ $2]$ $[2$ $2$ $1]$ 做成魔杖，得到最大权值 $2+3+1+4+4+5+2=21$ 。
---
#### 数据规模与约定
对于$100\%$的数据，保证：
- $1\le n\le 1000$，$1\le low\le h < 2^{31}$。
- $1 \leq l_i, m_i \le 10^5$