A. Жууху ба шоколад

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жуухуд $n × m$ квадрат нүднээс бүрдсэн том, тэгш өнцөгт хэлбэртэй, зураастай шоколад байв. Тэр яг зураасаар нь $k$ удаа зүсэхийг хүсэв. Үүний тулд дараах шаардлагуудыг хангах ёстой:

  • Зүсэлт бүр шулуун(хэвтээ эсвэл босоо) байх ёстой;
  • Зүсэлт бүр нь квадрат нүднүүдийн ирмэгээр байх ёстой(квадрат нүдийг хуваахыг хориглоно);
  • Зүсэлт бүр нь шоколадны дотор байх ёстой, бүх зүсэлт ялгаатай байх ёстой.

Доорх зурагт $5 × 6$ нүдтэй ​​шоколадыг $5$ хуваах боломжит арга замыг харуулж байна.

Жууху том шоколадыг $k$ удаа хувааж хэд хэдэн хэсэг болгоё гэж төсөөлөв. Хуваагдсан шоколадны хамгийн жижиг хэсгийг аль болох том байлгахыг хүсэв. Яг $k$ удаа хуваагаад хамгийн жижиг хэсгийг хамгийн том байлгах байлгах боломж юу вэ? Энэ тоо нь уг шоколадны квадрат нүднүүдийн тоо юм.

Оролт

Нэг мөрөнд гурван бүхэл тоо $n, m, k$ $(1 ≤ n, m ≤ 10^{9}; 1 ≤ k ≤ 2*10^{9})$ байна.

Гаралт

Хариултыг төлөөлсөн нэг бүхэл тоог хэвлэнэ. Хэрвээ том шоколадыг $k$ удаа хуваах боломжгүй бол $-1$ гэж хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 4 1
Гаралт
6
Оролт
6 4 2
Гаралт
8
Оролт
2 3 4
Гаралт
-1

Тэмдэглэл

Эхний жишээг доорх зурагт харуулснаар зүсэж чадна:

Хоёрдугаар жишээний тохиромжтой хуваалт ийм байна:

Гуравдугаар жишээ, $2 × 3$ нүдтэй шоколадыг $4$ удаа хувааж болохгүй.

Сэтгэгдлүүдийг ачааллаж байна...