小明很喜欢喝奶茶，在上大学这n天里，他给自己规定了每天喝k杯奶茶的目标，学校一共有m个奶茶店，其中第i个奶茶店会在第 Li天到第Ri天开业，每天将最多卖给小明 ci杯奶茶，每杯奶茶pi元钱，因为小明太喜欢喝奶茶啦，但是他还没有多少钱，他想知道自己在每天买完k杯奶茶之后，一共n天最少需要花多少钱。
特别的，如果第i天所有奶茶店卖给小明的奶茶都不够k杯，那么他只能喝到当天他能喝到的所有奶茶。第一行三个整数n,m,k分别表示小明计划喝n天奶茶，大学里一共有m家奶茶店，并且小明每天想喝k杯奶茶
下面m行每行四个正整数L,R,c,p,表示每家奶茶店的开业日期，关业日期，每天卖出的奶茶数以及奶茶价格
输出包含一个整数为小明每天喝k杯奶茶需要花费的最少钱数
【数据范围与约定】
对于100%的数据，n,k≤100,000，m≤200,000，1≤Li≤Ri≤n，1≤ci,pi≤1,000,000