### 问题描述 某电影院计划放映一批电影，为了吸引观众并最大化利润，电影院希望根据可供放映的时间 $M$ 和当前所有电影的时长和利润来确定一个最佳的电影放映计划。每部电影有时长和利润。为了确保观众的体验，电影院要求前后两部电影之间的放映时间间隔不小于一定值 $K$。 请你设计一个算法，帮助电影院确定一个最佳的电影放映计划使得利润最大化，你只需要给出最大的利润值即可。 ### 输入格式 输入的第一行包含两个整数，表示可供使用的放映时间长度 $M$ $(1 \leq M \leq 10^6)$ 和电影的数量 $N$，$(1 \leq N \leq 100)$。 接下来的 $N$ 行，每行包含两个整数，表示一部电影的持续时长和利润。第 $i$ 行的两个整数 $T_i$ 和 $P_i$（$1 \leq T_i ,P_i \leq 10^4$，表示第 $i$ 部电影的时长和利润。 最后一行包含一个整数 $K$，$(1 \leq K \leq 1000)$，表示电影之间的最小放映时间间隔。 ### 输出格式 输出一个整数，表示电影院通过最佳的电影放映计划所获得的最大利润。 ### 输入样例 ``` 300 4 120 300 90 200 150 400 180 500 30 ``` ### 输出样例 ``` 700 ``` ### 说明： 对于这个例子，最佳的电影放映计划其中之一如下： 1. 放映电影 $2$，持续时长 $90$ 分钟，利润 $200$。 2. 放映电影 $4$，持续时长 $180$ 分钟，利润 $500$。 因此，通过最佳的电影放映计划所获得的最大利润为 $200+500=700$。注意，还有其他电影放映计划可以获得 $700$ 的最大利润，但是最佳的计划必须满足电影之间的放映时间间隔不小于 $30$ 分钟。