Problem Description

Given \( n \) concentric sectors, determine the total area that is covered by at least \( k \) sectors.

Input Format

The first line contains three integers \( n \), \( m \), and \( k \). \( n \) represents the number of concentric sectors, and \( m \) represents the division of the angle interval \((- \pi, \pi]\) into \( 2m \) equal parts.

The next \( n \) lines each contain three integers \( r \), \( a_1 \), and \( a_2 \). This describes a sector centered at the origin with radius \( r \) and a central angle from \(\pi \times \frac{a_1}{m}\) to \(\pi \times \frac{a_2}{m}\) (where \( a_1 \) is not necessarily less than \( a_2 \)).

Output Format

Output an integer \( ans \) such that \(\frac{\pi}{2m} \times ans\) equals the total area covered by at least \( k \) sectors.

The data guarantees that the answer is within the range of \( 2^{63} - 1 \).

Sample Input and Output

Sample Input #1

3 8 2
1 -8 8
3 -7 3
5 -5 5

Sample Output #1

76

Sample Input #2

2 4 1
4 -4 2
1 -4 4

Sample Output #2

98

Notes

For \( 100\% \) of the data, \( 1 \leq n \leq 10^5 \), \( 1 \leq m \leq 10^6 \), \( 1 \leq k \leq 5000 \), \( 1 \leq r_i \leq 10^5 \), \(-m \leq a_1, a_2 \leq m \).

见题面 Input 部分

见题面 Output 部分