宗教问题

题目背景

在一个地区有许多种宗教,不同信仰的教徒经常发生矛盾,最为治安管理的人需要把这些人分开,以免矛盾激化。

题目描述

已知一个地方有M种宗教(编号为1—M),有N个教徒(编号为1—N),每个教徒信且只信一种宗教。现在要按顺序把这N个教徒分成一些集体,每个集体的危险值定义为这个集体中的宗教种数,且一个集体的宗教种类不能超过K种,否则就会无限危险, 问: 1.这N个教徒至少要分为几个集体, 2.这些集体的危险值总和至少为多少。

输入输出格式

输入格式


第一行三个正整数N M K,以空格隔开 第二行N个正整数,为每个教徒信的宗教编号

输出格式


第一行 一个正整数,为最少集体数 第二行 一个正整数,为最小危险值。

输入输出样例

输入样例 #1

10 4 3
1 2 3 4 3 4 3 2 1 2

输出样例 #1

3
6

说明

【样例解释】 最少集体数:1 2 3 // 4 3 4 3 2 // 1 2 共3个集体 最小危险值:1 2 // 3 4 3 4 3 // 2 1 2 2+2+2=6 【数据范围】 对于20%的数据 N≤20 对于50%的数据 N≤100 对于100%的数据 N≤1000 M≤20 1≤K<M