2264 - 【NOIP2014】D1T3 飞扬的小鸟

第 1 行有 3 个整数 n，m，k，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开
接下来的 n 行，每行 2 个用一个空格隔开的整数 X 和 Y，依次表示在横坐标位置 0~n-1上玩家点击屏幕后，小鸟在下一位置上升的高度 X，以及在这个位置上玩家不点击屏幕时， 小鸟在下一位置下降的高度 Y。
接下来 k 行，每行 3 个整数 P，L，H，每两个整数之间用一个空格隔开。每行表示一 个管道，其中 P 表示管道的横坐标，L 表示此管道缝隙的下边沿高度为 L，H 表示管道缝隙上边沿的高度(输入数据保证 P 各不相同，但不保证按照大小顺序给出)。

共两行。
第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。
第二行，包含一个整数，如果第一行为 1，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

【输入输出样例说明】

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

【数据范围】

• 对于 30%的数据:5≤n≤10，5≤m≤10，k=0，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;
• 对于 50%的数据:5≤n≤20，5≤m≤10，保证存在一组最优解使得同一单位时间最多点击屏幕3次;
• 对于 70%的数据:5≤n≤1000，5≤m≤100;
• 对于 100%的数据:5≤n≤10000，5 ≤ m ≤ 1000，0 ≤ k <n，0< X <m，0< Y <m，0< P <n，0 ≤ L < H ≤m， L+1 < H。