CF313D Ilya and Roads

Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as $ n $ holes in a row. We will consider the holes numbered from 1 to $ n $ , from left to right. Ilya is really keep on helping his city. So, he wants to fix at least $ k $ holes (perharps he can fix more) on a single ZooVille road. The city has $ m $ building companies, the $ i $ -th company needs $ c_{i} $ money units to fix a road segment containing holes with numbers of at least $ l_{i} $ and at most $ r_{i} $ . The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment. Determine the minimum money Ilya will need to fix at least $ k $ holes.

The first line contains three integers $ n,m,k $ $ (1

Print a single integer — the minimum money Ilya needs to fix at least $ k $ holes. If it is impossible to fix at least $ k $ holes, print -1. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.