启动机器

工厂中的机器需要花费1时间启动它，每台机器在工作\( t \)时间后会停止，即对于一台机器，启动它之后，它将在\( [x+1,x+t] \)时间内工作。当然，也可以对正在工作着的机器进行“维持启动”，同样花费1时间。

有n个任务需要这些机器来生产，每次生产需要至少有m台机器在工作。现在给出n个任务的到达时间，计算并输出最少需要启动机器的次数。如果无论如何也不能让至少m台机器同时工作，则任务无法完成，此时输出”-1″。

• \( 1 \leq n,m \leq 1000 \)
• \( 1 \leq t,w \leq 10^9 \)

测试用例

输入1

2 5 2
1 2

输出1

2

输入2

1 1 10
1

输出2

-1

渡河

阿强一行有N人，第i人的体重为\(a_i\) ，现在阿强一队人面前有一条河挡住了去路，不过他们可以利用小船把大家送到河对岸。这艘船的运动有这样的特性：船最多只能运两人，并且渡河时间（秒）恰等于是两人的体重较大者。现给出阿强一队人的体重，计算阿强最短可能用多久渡河。

输入T组数据，每组数据包含N个正整数，表示这一队人的体重。

测试用例

输入数据

2
4
2 11 9 12
4
2 3 8 7

输出数据

37
19

二叉树计数

一个二叉树有N个结点，给出每个结点所在的深度（根结点的深度为0），计算结点数满足给出的数据的二叉树有多少，由于数据可能较大，输出对\( 10^9 + 7\) 取余的结果。

车辆调度

Alice是某城市的汽车调度员，现在Alice所负责的派车点将为城市A,B两区域派车，每辆车派去A地和B地对于Alice的收益是不同的。Alice的派车点有N辆车，现在分别给出每辆车派去两地的收益，计算向A地派去a辆车以及B地派去b辆车的最大收益。\( 0 \lt a+b \leq N \leq 2000 \).
输入第一行给出N,a,b，接下来N行，每行两个数字分别表示这辆车派去A和派去B的收益。输出一个数字，表示将a+b辆车派至目的地能获得的最大收益。

测试用例

输入数据

5 2 2
4 2
3 3
5 4
5 3
1 5

输出数据

18

编码协议

某种编码协议将数据编为十六进制0-9及A-F，但是’0010’是特殊字串在这种协议中不允许出现，现在给出一串十六进制的数字，判断最少删除几个字符才能使这一串十六进制数中不含有非法字串”0010″

插广告

有N段视频，每段视频长度为\( L_i \)秒，现在要向这N段视频中共计插入M条广告，而两次广告之间不能出现的太频繁否则会降低用户体验，可以在开始前和结束后各插一条广告。计算如何使相邻两条广告出现时间间隔最小值尽可能大，输出这个最大秒数。

数字之和取余

给定n(\( n \leq 35 \))个数字的数组，从中任选k个求和，计算k个数字之和与给定常数m取余可能的最大值。

旅行路线

Alice在暑假游玩了好多地方，但不记得旅行了多少次，根据Alice给出的火车票起始城市，认为城市能首尾相接成为一个闭环则完成一次旅行，计算Alice在暑假中进行了几次旅行。数据保证所有城市都在一个闭环中出现。

测试用例

输入数据

6
beijing nanjing
nanjing guangzhou
guangzhou shanghai
shanghai beijing
fuzhou beijing
beijing fuzhou

输出数据

2

送外卖

Alice是区域外卖调配员，为了让整个区域的外卖员能高效配送，Alice将订单按以小区为单位分组，尽量使外卖员在同一小区多送几份外卖。Alice根据外卖寄送可以知道a订单和b订单是同一小区的。现在Alice有N个小区以及M组数据，统计一下这M组数据中哪些订单都是一个小区，按订单号从小到大输出。这些组中按首个订单号递增的顺序输出。

测试用例

输入数据

5 5
1 2
2 2
3 1
4 2
5 4

输出数据

1
1 2 3 4 5