## Educational DP Contest AtCoder W - Intervals

View as PDF

Points: 20
Time limit: 1.0s
Memory limit: 1G

Problem types

Consider a string of length consisting of 0 and 1. The score for the string is calculated as follows:

• For each , is added to the score if the string contains 1 at least once between the -th and -th characters (inclusive).

Find the maximum possible score of a string.

#### Constraints

• All values in input are integers.

#### Input Specification

The first line will contain two integers and .

The next lines will each contain three integers, .

#### Output Specification

Print the maximum possible score of a string.

#### Sample Input 1

5 3
1 3 10
2 4 -10
3 5 10

#### Sample Output 1

20

#### Explanation For Sample 1

The score for 10001 is .

#### Sample Input 2

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

#### Sample Output 2

90

#### Explanation For Sample 2

The score for 100 is .

#### Sample Input 3

1 1
1 1 -10

#### Sample Output 3

0

#### Explanation For Sample 3

The score for 0 is .

#### Sample Input 4

1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

#### Sample Output 4

5000000000

#### Explanation For Sample 4

The answer may not fit into a 32-bit integer type.

#### Sample Input 5

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

#### Sample Output 5

10

#### Explanation For Sample 5

For example, the score for 101000 is .