사랑의 상처

이 문제는 굵게 표시한 $M$의 범위를 제외하면 사랑의 흉터와 동일한 문제입니다.

저택의 꽃밭에는 셰리가 좋아하는 $N$가지 색깔의 장미가 자라고 있었어요. 이 꽃밭에는 사시사철 꽃이 계속 자라는 마법이 걸려 있어서, 각 색깔의 장미는 무한히 많은 것이나 다름없었죠. 어느 날, 셰리는 장미를 몇 송이 따서 리본으로 묶어 소중한 친구를 위한 꽃다발을 만들어 보려고 했어요.

다만 너무 많은 장미를 사용하면 셰리에게 꽃다발이 너무 무거워지기 때문에 사용된 장미의 개수는 $M$송이 이하여야 해요. 또한 같은 색의 장미 두 송이가 함께 꽃다발에 들어가면 꽃다발에 상처를 하나 남깁니다. 즉, 꽃다발에서 서로 다른 두 장미를 순서 없이 골랐을 때 두 장미의 색이 같은 경우의 수 만큼 상처가 생깁니다. 상처가 너무 많으면 꽃다발이 파괴되어 버리기 때문에 상처의 개수는 $K$개 이하여야 합니다.

셰리는 사랑을 한껏 담은 커다란 꽃다발을 만들고 싶었습니다. 꽃다발을 구성할 수 있는 장미의 최대 개수를 구해주세요.