Lát sàn (Floor Tiling)

Nguồn: Sở Giáo dục và Đào tạo Hà Nội — Kỳ thi chọn HSG thành phố và chọn đội tuyển HSG dự thi Olympic các môn văn hóa, lớp 12 THPT năm học 2026–2027

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $X$ mặt sàn hình chữ nhật có cùng kích thước là $M$ mét và $N$ mét. Chủ đầu tư muốn sử dụng nhiều nhất những viên gạch nguyên vẹn hình vuông có kích thước cạnh là $K$ xăng-ti-mét (cm) để lát toàn bộ mặt sàn. Phần mặt sàn còn lại sẽ được sử dụng gạch thẻ để trang trí.

Hãy tính số lượng viên gạch nguyên vẹn hình vuông nhiều nhất được sử dụng để lát tất cả các mặt sàn.

Input

Gồm bốn dòng:

• Dòng thứ nhất gồm một số nguyên dương $X$.
• Dòng thứ hai gồm một số nguyên dương $M$.
• Dòng thứ ba gồm một số nguyên dương $N$.
• Dòng thứ tư gồm một số nguyên dương $K$.

Output

In ra một số nguyên dương là số lượng viên gạch nguyên vẹn hình vuông nhiều nhất có thể sử dụng.

Subtask

• Subtask 1 (25 điểm): $X=1$, $1\le M,N\le 10$, $10\le K\le 100$.
• Subtask 2 (35 điểm): $1\le X\le 10$, $1\le M,N\le 100$, $1\le K\le 100$.
• Subtask 3 (40 điểm): $1\le X\le 100$, $1\le M,N\le 10^3$, $1\le K\le 100$.

Ví dụ

Input

2
1
2
6

Output

1056

Giải thích

Có $2$ mặt sàn, mỗi mặt sàn có kích thước $1\text{ m}\times 2\text{ m}$, tương ứng $100\text{ cm}\times 200\text{ cm}$. Viên gạch vuông có kích thước $6\text{ cm}\times 6\text{ cm}$. Trên mỗi mặt sàn sử dụng được $528$ viên gạch nguyên vẹn, nên trên $2$ mặt sàn sử dụng được $528\times 2=1056$ viên.