[SHOI2013] 扇形面积并

题目描述

![](https://cdn.luogu.com.cn/upload/pic/11825.png) 给定 n 个同心的扇形,求有多少面积,被至少 $k$ 个扇形所覆盖。

输入输出格式

输入格式


第一行是三个整数 $n$,$m$,$k$。$n$ 代表同心扇形个数,$m$ 代表将 $(−\pi ,\pi]$ 的角度区间平均分成 $2m$ 份。 从第二行开始的 $n$ 行,每行三个整数 $r,a_1,a_2$。描述了一个圆心在原点的扇形,半径为 $r$,圆心角是从弧度 $\pi\times \frac{a_1}{m}$ 到 $\pi\times \frac{a_2}{m}$($a_1$ 不一定小于 $a_2$)。

输出格式


输出一个整数 $ans$ ,$\frac{\pi}{2m}\times ans$ 等于至少 $k$ 个扇形所覆盖的总面积。 数据保证答案在 $2^{63} - 1$ 范围内。

输入输出样例

输入样例 #1

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

输出样例 #1

76

输入样例 #2

2 4 1
4 -4 2
1 -4 4

输出样例 #2

98

说明

对于 $100\%$ 的数据,$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$。