#101909. [BZOJ 1909] Berth Allocation

一个港口被分成了 M个区域(1

Input contains many test sets. A test data set is defined as follow: The first line of test data set is two integers: m and n, separated by one or more spaces(1≤m≤10, 1≤n≤100000). m is the number of sections in the port, and n is the number of ships. The next m lines, one positive integer r (that means the length of the section is r hundred meters long) per line. The length of each section does not exceed 10000 hundred meters. The next n lines gives one ship information on each line, with three non-negative integers s, e, sec (0≤s≤e,1≤sec≤m) per line, s is the arrival time of the ship, e is the departure time of the ship, and sec is the section which the ship should be berthed in. Input is ended by EOF. You can assume that all the input data are legal.

For each test data set you should output one integer, the maximal number of the berthed ships, per line.

样例输入

2 6  //二个区域,六只船
3   //区域的大小
3  //区域的大小
1 2 1  //每只船来去的时间及它应该要停泊的区域号
1 2 1
1 2 1
1 2 1
1 2 2
1 2 2

1 3
2
1 3 1
2 6 1
2 8 1

1 4
2
1 3 1
5 6 1
2 8 1
4 10 1

样例输出

5
2
3

2004年广东省大学生程序竞赛试题 Problem B