Знаменитое объединение художников «Калевич жив!» поставило на поток производство шедевров. Объединение состоит из n художников, которые решили следующим образом организовать свою работу.

Каждый из художников будет использовать только один закрепленный за ним цвет. Цвета для всех художников различны, будем считать что первый художник использует первый цвет, второй художник — второй цвет, и так далее. Каждый шедевр будет содержать все эти цвета. Чтобы наложить j-й цвет на i-й шедевр, j-му художнику потребуется t_ij единиц времени.

Во всем нужен порядок, поэтому работа художников упорядочена по следующим правилам:

• каждый шедевр сначала обрабатывается первым художником, потом вторым и т.д., то есть после окончания обработки j-м художником шедевр должен быть обработан (j + 1)-м (если j < n);
• каждый из художников работает над шедеврами по порядку: сначала работает над первым шедевром, потом над вторым и так далее;
• каждый художник может одновременно работать не более чем над одним шедевром, но времени на отдых им не требуется;
• как только j-й художник заканчивает работу над шедевром, тот мгновенно передается следующему художнику.

Считая, что художники приступят к работе в момент времени 0, найдите для каждого шедевра момент времени, когда он будет готов к продаже.