题目描述

一座展馆准备调整展品的陈列方式。展厅中共有 $n$ 件展品，从左到右排成一列。展品分为 $m$ 类，第 $i$ 件展品的类别为 $a_i$，价值为 $v_i$，其中价值可以为负数。

管理员可以撤走任意多件展品，也可以一件不撤。撤走展品后，剩余展品的相对顺序保持不变，且任意两件相邻展品的类别必须不同。

请你求出剩余展品的价值总和最大是多少。允许撤走全部展品，此时价值总和为 $0$。

输入格式

第一行包含两个整数 $n,m$，分别表示展品的数量和类别数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,v_i$，分别表示从左到右第 $i$ 件展品的类别和价值。

输出格式

输出一行，包含一个整数，表示满足要求的剩余展品价值总和的最大值。

样例输入 1

3 2
1 6
2 -2
1 7

样例输出 1

11

样例 1 解释

保留全部三件展品时，类别依次为 $1,2,1$，相邻展品的类别均不同，价值总和为 $6-2+7=11$，这是能够取得的最大值。

样例输入 2

3 1
1 -1
1 -3
1 -2

样例输出 2

0

样例 2 解释

所有展品的价值均为负数。撤走全部展品可使价值总和为 $0$，保留任何展品都无法得到更大的值。

数据范围与子任务

对于所有测试数据，保证$1\le n\le150000$，$1\le m\le n$，$1\le a_i\le m$，$-10000\le v_i\le10000$。

每个子任务内的正式测试全部通过，才获得该子任务的分数。