Alice 喜欢玩一款名为“Steadily Growing Steam”（简称 SGS）的卡牌游戏。

在这个游戏中，每个玩家扮演不同的角色并拥有不同的技能。玩家从牌堆中抽取卡牌并使用它们进行游戏。每张卡牌都有一个数字标签 $t_i$，即点数。此外，每张卡牌还有一个价值 $v_i$。

现在 Alice 正在和 Bob 玩这个游戏。根据 Alice 角色的技能，她可以让 Bob 展示牌堆顶部的 $n$ 张卡牌。之后，Bob 必须从这 $n$ 张卡牌中选择一些卡牌，并将选出的卡牌分成两个集合，使得这两个集合中卡牌的点数之和相等。换句话说，如果其中一个集合是 $S$，另一个是 $T$，则 $S \cap T = \emptyset$ 且 $\sum_{i \in S} t_i = \sum_{j \in T} t_j$（注意 $S \cup T = \{1, 2, \dots, n\}$ 不一定成立）。然后，Alice 获得集合 $S$ 中的所有卡牌，Bob 获得集合 $T$ 中的所有卡牌。

然而，根据 Bob 角色的技能，在选择这两个集合之前，他可以选择至多 $k$ 张不同的卡牌并将它们的点数翻倍。换句话说，他可以选择一个序列 $\{a_1, a_2, \dots, a_r\}$，其中 $(1 \le a_1 < a_2 < \dots < a_r \le n, 0 \le r \le k)$，并对于每个 $i(1 \le i \le r)$，将 $t_{a_i}$ 变为 $2t_{a_i}$。之后，他可以继续选择这两个集合。

Alice 和 Bob 是游戏中的搭档。现在给定牌堆中的 $n$ 张卡牌，他们想知道最终获得的卡牌价值之和的最大值。换句话说，确定在所有有效方案（选择卡牌翻倍，然后选择卡牌并将其分成点数之和相等的两个集合 $S, T$）中，$\sum_{i \in S \cup T} v_i$ 的最大值并输出。

输入格式

第一行包含两个整数 $n (1 \le n \le 100)$ 和 $k (0 \le k \le n)$，分别表示展示的卡牌数量和 Bob 可以选择翻倍的卡牌的最大数量。

第 $i+1$ 行包含两个整数 $v_i (|v_i| \le 10^9)$ 和 $t_i (1 \le t_i \le 13)$，分别表示第 $i$ 张卡牌的价值和点数。

输出格式

输出一行，包含一个整数，表示 Alice 或 Bob 可以获得的卡牌价值之和的最大值。

样例

输入 1

4 1
10 1
-5 3
5 1
6 1

输出 1

21

说明

一种可能的方案： 将 $t_1$ 翻倍并选择 $S = \{1\}, T = \{3, 4\}$，此时两个集合的点数之和均为 $2$，卡牌价值之和为 $10 + 5 + 6 = 21$。