#P15T14. 加州旅馆

加州旅馆

题目描述

小 W 开了一家旅店,叫做 WWW 旅馆。

一天,旅馆来了 nn 位客人。小 W 需要把他们都安排在酒店的某一层中。每个房间中只能安排一位客人。

这一层共有 mm 间房间,这 mm 间房间都是空的,且这 mm 间房间形成了一个环形,即对于所有的 1xm1 \le x \le m,都有第 xx 间房间与第 ((xmodm)+1)((x \bmod m)+1) 间房间相邻,第 ((xmodm)+1)((x \bmod m)+1) 间房间与第 xx 间房间相邻,其中 xmodmx \bmod m 表示 xx 除以 mm 得到的余数。

nn 位客人都十分挑剔,他们希望与自己的房间相邻的房间中没有人。对于某一位客人,若与他的房间相邻的房间中,有 kk 间房间有人,则这位客人会产生 kk 点愤怒值。

你需要帮助小 W 安排房间,使得所有客人的愤怒值之和最小,并输出所有客人的愤怒值之和的最小值。

输入格式

两个整数 n,mn,m

对于 100%100\% 的数据,1n1001 \le n \le 1003m1003 \le m \le 100,保证 nmn \le m

输出格式

一个整数,表示所有客人的愤怒值之和的最小值。

3 5
2