SP11875 POSAO - Jobs

小 Domagoj 面临大量的工作，这些工作被安排在一个 $N \times N$ 的矩阵中，每个单元格代表一项具体的任务。要开始进行单元格 $(x, y)$ 上的任务，必须先完成位于 $(x, y-1)$ 和 $(x-1, y)$ 的任务（如果这些单元格存在）。  图中灰色单元格显示了完成某项工作所需先完成的任务。 Domagoj 拥有 $K$ 台计算机来帮助他完成这些任务。每台计算机在一秒内最多能执行一个任务，而不需要每台计算机在每一时刻都执行任务。请帮他合理安排这些任务，确保用最短的时间完成所有的工作。

输入的第一行包含两个整数 $N$ 和 $K$，分别表示矩阵的大小和计算机的台数。

输出完成所有任务所需的最短时间。 **本翻译由 AI 自动生成**