问题描述

        小喵喵和小聪聪从小就是好朋友,他们经常在一起玩耍。如今小喵喵已经厌倦了自己居住的环境,想请小聪聪为她建一个新家。

        小喵喵天生多才多艺,对多种乐器颇有研究。对于生活中常见的图形,她对圆形很感兴趣,因此小聪聪决定为她建一个圆形的新家。

        我们设新家在一个平面直角坐标系上,其中新家的圆心为平面直角坐标系的原点。

        小聪聪有一把神奇的剪刀,他定义了一个值m,以等分[-\pi,\pi]的弧度(详见样例)。他还有一支神奇的画笔,将进行n次“铺地毯”操作。对于第i次铺地毯操作,他将设定一个半径r_i,起始位置s_i,终止位置t_i,然后从圆心角\frac{\pi s_i}{m}到圆心角\frac{\pi t_i}{m}这部分区域逆时针铺上一个扇形地毯。

        小喵喵想到了一个奇怪的问题,她想知道有多大的面积被至少铺过k次地毯。这个问题一下就难倒了聪明的小聪聪。现在小聪聪求助于你,你能帮他解决这个问题吗?为了方便表达,设答案的值为T,你只需要输出T\times \frac{2m}{\pi}的值即可。

 

输入格式

        输入数据第一行包含三个整数nmk,含义如题目描述中所述。

        接下来n行,每行描述一次铺地毯操作。第i行有三个整数r_is_it_i,含义如题目描述中所述。

 

输出格式

        输出一行,包含一个整数,表示T\times \frac{2m}{\pi}的值。

 

样例输入

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

 

样例输出

76

 

样例解释

        样例中的内容如下图所示:

 

数据规模与约定

        所有测试点的数据规模如下:

        对于全部测试数据,T\times\frac{2m}{\pi}\leq2^{63}-1-m\leq s_i,t_i\leq ms_i\neq t_i