5743: Exterminate

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:26 Solved:4

Description

不论如何伸出手

也望尘莫及的地方 就是我们相恋的地方

在偏安一隅

目送时光的流走 凝望着我们向前迈进

历史的年轮滚滚不息,为着大地上连绵的战事不止叹息。光荣战役已经延续了多年,你们即将获胜,然而敌军发起了最后的挣扎。

敌人大军压城而来,共有n名战士,每名战士有一个威力值Wi。幸运的是,友方守护者Nebuchadnezzar已经做好了充分准备,他的魔力阵可以直接消灭第一个威力值模3余1的敌军士兵,但是对于每一个满足条件的威力值,这个魔法只能消灭一个敌军。

对于所有逃离魔法阵的敌人,你必须不惜一切代价阻止他们,为队友争取时间。但是,由于魔力的匮乏,你无法在攻击过程中汲取法力值。所以,你只能将威力值排序前k大的数值的敌人消灭,如果这个数值的敌人不止一个,他们都会被消灭。

为了梦想中的胜利,你希望知道,你最多能消灭多少个敌人。

Input

第一行,两个正整数n,k,表示敌人的数量和你能消灭的威力数值的个数。

第二行,n个正整数W1..Wn. 表示敌人的威力值。

题目满足1≤n≤10^5 , 1≤k≤10^5 , 且k<m(m为逃离魔法阵的敌人威力个数)

1≤Wi≤10^7.

Output

一行,一个非负整数,表示你能消灭的敌人个数

Sample Input Copy

7 2
2 4 9 10 4 2 4

Sample Output Copy

3

HINT

Nebuchadnezzar的魔法阵消灭了威力值为10的敌人和第一个威力值为4 的敌人。

剩余的敌人按照威力值从大到小排序为9,4,4,2,2.

你能消灭前2大的威力数值,也就是9和4,所以威力值为9,4,4的3个敌人被消灭。

时间限制:1s,空间限制:256MB

Map,Sort