题目描述

给定 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

输入 #1

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

输出 #1

76

输入输出样例 #2

输入 #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$。