No submission language available for this problem.

题目描述

在一条数轴上散落着$n$个魔法珠，第$i$个魔法珠位于$X_i$，且能量值为$E_i$，属性为$C_i$。魔法珠可以提供不同的魔法，只有不超过7种的属性，按照属性从1-7编号。

现在蜗牛老师希望从左往右依次选取恰好$m$个魔法珠，因为魔法的相互影响，在选取魔法珠的过程中，选取的相邻的魔法珠属性不能相同。

现在问，满足以上要求的情况下，选取$m$个魔法珠的能量值总和为多大？

输入格式

第一行两个整数$n,m$,表示魔法珠总数和要挑选的魔法珠总数

接下来$n$行，每行三个整数$X_i,E_i,C_i$.

输出格式

一行一个整数，表示能获得的能量的最大值，如果不能合法的选出$m$个，输出$-1$。

样例数据

input

5 2
-1 1 1
0 2 3
1 3 3
-2 5 3
4 5 5

output

10

选取在-2，4的两个魔法珠，能量总和为5+5=10

input

2 2
-1 2 2
-3 2 2

output

-1

由于n==m，所有魔法珠都得选，但两个魔法珠属性值相同，无法都选，故没有合法方案，答案为-1.

input

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

output

31

数据规模与约定

对于$100\%$ 数据保证 $1 \le n,m \le 3000$, $-10^9 \le X_i \le 10^9$,$1 \le E_i \le 10^9$, $1 \le C_i \le 7$, 所有 $X_i$ 互不相同。

时间限制：$1.5 \text {s}$

空间限制：$1024 \text {MB}$

Background

Special for beginners, ^_^

Description

Given two integers x and y, print the sum.

Format

Input

Two integers x and y, satisfying $0\leq x,y\leq 32767$ .

Output

One integer, the sum of x and y.

Samples

123 500

623

Limitation

1s, 1024KiB for each test case.