oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

variety Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

Peanut is eating at a KBBQ restaurant, with N different types of meat, numbered 0 to N-1. Unlike most KBBQ places, the food is not free flow. There are M orders that you can make, with order i costing Ci dollars and giving you 1kg of each type of meat numbered between Ai and Bi inclusive.

Peanut wishes to try a wide variety of meat, but doesn't want to get too full, so he wants to eat exactly 1kg of each type of meat. However, as with most KBBQ restaurants, food wastage is charged at W dollars per kg. For each kg of meat Peanut orders but doesn't eat, he would have to pay an additional W dollars.

Help Peanut figure out the minimum amount of money he must spend, in dollars, to try exactly 1kg of every type of meat.

Input

The first line of input will contain three integers, N, M and W.

The next M lines of input will contain three integers each, Ai, Bi and Ci.

Output

The output should contain exactly one integer, the minimum amount of money Peanut must spend, in dollars. If no possible solution will allow Peanut to try every type of meat, print -1.

Limits

For all subtasks: 1 ≤ N, M ≤ 300 000, 0 ≤ Ci, W ≤ 109, 0 ≤ Ai ≤ Bi < N.

Subtask 1 (8%): Ai = Bi.

Subtask 2 (12%): Ci = 1, W = 0.

Subtask 3 (24%): W = 0.

Subtask 4 (23%): 1 ≤ N, M ≤ 1000.

Subtask 5 (33%): No additional constraints.

Sample Input

3 3 1
0 1 2
1 2 2
0 2 6

Sample Output

5

Explanation

It is optimal for Peanut to buy the first and second orders, costing a total of $4. Since he will get 2kg of meat 1, he will pay a $1 fine for wasting 1kg of food. This will cost a total of $5.

Tags

Graph Theory, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
18201s256MBMinimum
212201s256MBMinimum
324401s256MBMinimum
423211s256MBMinimum
5331011s256MBMinimum
6011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o variety -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.