Canadian Computing Competition: 2014 Stage 1, Senior #4

You are laying \(N\) rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors.

You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the \(x\) -axis or the \(y\) -axis (that is, there are no "diagonal" pieces of glass).

You would like to know the total area of the finished stained glass window with a tint-factor of at least \(T\) .

Input Specification

The first line of input is the integer \(N\) ( \(1 \le N \le 1\,000\) ), the number of pieces of glass. The second line of input is the integer \(T\) ( \(1 \le T \le 1\,000\,000\,000\) ), the threshold for the tint-factor. Each of the next \(N\) lines contain five integers, representing the position of the top-left and bottom-right corners of the \(i\) th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order \(x_l\ y_t\ x_r\ y_b\ t_i\) , where the top-left corner is at \((x_l, y_t)\) and the bottom-right corner is at \((x_r, y_b)\) , and tint-factor is \(t_i\) . You can assume that \(1 \le t_i \le 1\,000\,000\) . The top-most, left-most coordinate where glass can be placed is \((0, 0)\) and you may assume \(0 \le x_l < x_r \le K\) and \(0 < y_t < y_b \le K\) .

The following additional constraints will apply.

• At least 10% of the marks will be for test cases where \(N \le 100\) and \(K \le 100\) ;
• at least 30% of the marks will be for test cases where \(N \le 1\,000\) and \(K \le 1\,000\) ;
• at least 40% of the marks will be for test cases where \(N \le 100\) and \(K \le 1\,000\,000\,000\) ;
• the remaining marks will be for test cases where \(N \le 1\,000\) and \(K \le 1\,000\,000\,000\) .

Output Specification

Output the total area of the finished stained glass window which has a tint-factor of at least \(T\) . All output will be less than \(2^{64}\) , and the output for some test cases will be larger than \(2^{32}\) .

Sample Input

4
3
11 11 20 15 1
13 8 14 17 2
17 8 18 17 1
12 12 19 13 1

Output for Sample Input

5

Explanation of Output for Sample Input

There are 4 pieces of glass used. There are two regions of glass which have a tint-factor greater than or equal to 3: one region between \((13, 11)\) and \((14, 15)\) (which has tint-factor of 3, except for a unit square with tint-factor 4), and another region between \((17, 12)\) and \((18, 13)\) (with tint-factor 3). In total, these two regions have 5 square units of glass with tint-factor greater than or equal to 3, as shown on the diagram below.