О нет! Скоро закончится время, когда еще можно подать заявку на стажировку в IT компанию, а вы медлили, участвуя в контестах вместо этого! (Давайте пока притворимся, что в наше неопределенное время можно будет найти работу.)

Вы сделали много проектов по программированию. Существует ровно $$$n$$$ типов проектов и вы сделали $$$a_i$$$ проектов типа $$$i$$$. Ваше резюме имеет ограниченный размер, но вы хотите аккуратно выбрать проекты, чтобы максимизировать шанс того, что вас возьмут на работу.

Вы хотите включить несколько проектов одного типа, чтобы подчеркнуть вашу компетентность, но вы также не хотите включать их так много, что среди них начнут появляться некачественные проекты. Поэтому, вы придумали следующую формулу, которая является хорошим индикатором того, что вас возьмут на работу:

$$$$$$ f(b_1,\ldots,b_n)=\sum\limits_{i=1}^n b_i(a_i-b_i^2). $$$$$$

Здесь $$$b_i$$$ обозначает количество проектов типа $$$i$$$, которое вы включите в ваше резюме. Конечно, вы не можете включить в резюме больше проектов, чем вы сделали, поэтому для всех $$$i$$$ должно быть выполнено $$$0\le b_i \le a_i$$$.

В вашем резюме хватает места для $$$k$$$ проектов, и вы абсолютно точно не будете приняты на работу, если в вашем резюме будет пустая строчка. Поэтому вы хотите, чтобы было выполнено $$$\sum\limits_{i=1}^n b_i=k$$$.

Найдите значения $$$b_1,\ldots, b_n$$$, которые максимизируют значение $$$f(b_1,\ldots,b_n)$$$ при том, что все описанные условия выполнены.