Европейская математическая олимпиада среди девочек (EGMO). 2016 год. Румыния

Пусть даны целые числа $k$ и $n$ такие, что $k \geq 2$ и $k \leq n \leq 2 k-1$. На клетчатую доску размера $n \times n$ последовательно выкладывают плитки любого из двух видов $1 \times k$ и $k \times 1$ так, что каждая плитка покрывает ровно $k$ клеток и никакие две плитки не перекрываются. Этот процесс заканчивается, когда невозможно добавить ни одной плитки. Найдите наименьшее возможное количество выложенных плиток.