Description

Given $n$ concentric sectors, find how much area is covered by at least $k$ sectors.

Input Format

The first line contains three integers $n$, $m$, $k$. Here, $n$ is the number of concentric sectors, and $m$ means the angle interval $(-\pi, \pi]$ is evenly divided into $2m$ parts.

From the second line, each of the next $n$ lines contains three integers $r, a_1, a_2$. Each line describes a sector centered at the origin with radius $r$, whose central angle ranges from radians $\pi \times \frac{a_1}{m}$ to $\pi \times \frac{a_2}{m}$ ($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.

It is guaranteed that the answer is within the range $2^{63} - 1$.

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

76

2 4 1
4 -4 2
1 -4 4

98

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le k \le 5000$, $1 \le r_i \le 10^5$, $-m \le a_1, a_2 \le m$.

Translated by ChatGPT 5