Олимпиада Туймаада по математике. Младшая лига. 2014 год

На бумаге с шестиугольными клеточками отметили "параллелограмм" $k\times \ell$ клеток (он состоит из $k$ горизонтальных рядов по $\ell$ клеток в каждом; для примера на рисунке изображен параллелограмм $3\times 4$ ).

В~этом параллелограмме выбрали набор непересекающихся сторон клеток, которые разбивают все узлы на пары. Сколько вертикальных отрезков может быть в таком наборе? ( Т. Дошилич )