Вы, наверное, слышали про задачу о дележе торта. Если два человека хотят справедливо разделить кусок торта, то один человек должен разрезать кусок пополам, а другой — выбрать, кому достанется какая половина. У Алисы и Боба есть несколько кусочков пирога, и, вместо того, чтобы разрезать каждый кусочек пополам, они договорились, что каждый кусочек будет съеден одним человеком.
Они решили разделить кусочки следующим образом. Сначала они определили порядок, в котором кусочки будут распределены. У них есть специальная фишка, называемая «решающий», изначально она находится у Боба. Пока не все кусочки распределены, тот, у кого находится фишка, дает очередной кусочек пирога по своему усмотрению одному участнику дележа, а фишку — другому. Так продолжается, пока все кусочки не будут распределены.
Так как все кусочки превосходного качества, каждый участник хочет максимизировать суммарный размер кусочков пирога, которые достанутся ему. Предполагая, что оба участника принимают решения оптимально, сколько пирога получит каждый?
Выходные данные
Выведите два целых числа. Сначала выведите суммарный размер кусочков, которые достанутся Алисе, а затем суммарный размер кусочков, которые достанутся Бобу, если оба участника действуют оптимально.
Примечание
В первом примере Боб должен взять кусок размера 141 себе и отдать фишку Алисе. Затем Алиса отдаст кусочек размера 592 Бобу, а фишку оставит себе, чтобы забрать себе кусочек размера 653.