P84460

W

难度 未定 贪心
讨论 统计 3通过 8提交 37.5%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

小 L 很喜欢字母 W。

小 L 想让你构造一个正整数序列 a,要求:

  1. 这个序列有 n 个数,下标为 [1,n]。
  2. \sum\limits_{i=1}^na_i=m。

请你求: \sum\limits_{i=1}^n(a_i\bmod k) 的最大值。

输入

一行,3 个正整数 n,m,k。

输出

一行,表示这个最大值。

样例

样例 1
输入
3 5 3
输出
5
样例 2
输入
3 11 3
输出
5

提示

【样例解释】

对于样例一,可构造出序列 [2,1,2],答案为 5。

【数据范围】

子任务编号n,km分数
0\le 10\le 10^{18}20
1\le 500^20
3\le 10^{9}^60

对于 100\% 的数据,保证 2\le n\le k\le 10^9,m\le 10^{18}。

来源

luogu

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交