100 #2041. 铺地毯

铺地毯

铺地毯

题目背景

帅气的杨老师为你们准备一个独特的刷题典礼,他在会场的一片矩形区域铺上一些正方形地毯。

题目描述

这片矩形区域长 aa 米,宽 bb 米。地毯为边长为 cc 米的正方形。

他想要知道,在地毯不进行裁切且两两不重叠的前提下,能否使用若干张这种地毯铺满整个矩形,如果可以铺满,那么铺满整个矩形需要多少张地毯。

输入格式

输入共一行,为三个正整数 a,b,ca, b, c,分别表示矩形区域的长、宽和地毯的边长。

输出格式

输出共一行。

如果无法使用若干张这种地毯铺满整个矩形,输出一行一个 -1

如果可以使用若干张这种地毯铺满整个矩形,输出一行一个正整数,代表铺满整个矩形需要的地毯的数量。

样例 #1

样例输入 #1

20 15 5

样例输出 #1

12

样例 #2

样例输入 #2

39 17 24

样例输出 #2

-1

提示

样例 1 解释

将地毯按如下方式放置 1212 张即可铺满整个矩形。

样例 2 解释

容易发现,不存在任何一种方式可以使用若干张此类地毯铺满整个矩形。

数据规模与约定

对于所有测试点:1a,b10181 \leq a, b \leq 10 ^ {18}1c10181 \leq c \leq 10 ^ {18}。保证如果存在答案,最终答案不超过 101810 ^ {18}

测试点 a,ba, b cc 特殊性质
1,21, 2 103\leq 10 ^ 3
3,43, 4 1018\leq 10 ^ {18} =1= 1
55 1018\leq 10 ^ {18} 保证 a,b<ca, b < c
6106 \sim 10