На бројната оска, која е обоена во црно, дадени се три затворени интервали [L_i, R_i], за i = 1, 2, 3. Овие интервали означуваат дека од точката L_i до точката R_i оската е обоена во црвено.

Вие може да правите операција поместување, а вашата цел е да го максимизирате црвениот дел на бројната оска по извршување на најмногу K операции поместување.

Со една операција поместување, можете да изберете кој било од трите интервали и да го поместите во лево или во десно за точно една единица. Поточно, за избраниот интервал [L_i, R_i], можете да ги намалите и L_i и R_i за 1 (поместување лево), или пак да ги зголемите и L_i и R_i за 1 (поместување десно).

При поместување во лево може да се случи почетокот на интервалот да се помести и кон негативниот дел од бројната оска.

Определете ја максималната можна должина на бројната оска која ќе биде обоена во црвено (вкупната должина на сите делови) по извршување на најмногу K операции.

Влез

Во првиот ред се дадени 2 цели броеви L₁ и R₁, разделени со едно празно место.
Во вториот ред се дадени 2 цели броеви L₂ и R₂, разделени со едно празно место.
Во третиот ред се дадени 2 цели броеви L₃ и R₃, разделени со едно празно место.
Во четвртиот ред е даден еден цел број K.
Притоа важи: 0 ≤ L_i, R_i, K ≤ 10¹⁵, за i = 1, 2, 3.

Забелешка. За 60% од поените важи: 1 ≤ K ≤ 1 000 000.
За дополнителни 20% важи: L₁ = L₂ и R₁ = R₂.

Излез

Во еден ред отпечатете ја бараната максимална должина на бројната оска обоена во црвено.

Ограничувања

Временско ограничување: 100 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
1 3
2 4
3 5
2

излез
6

влез
1 2
6 7
6 7
1

излез
3

Објаснување за првиот пример: Може да извршиме една операција на првиот интервал, со тоа што ќе го поместиме во лево ([1, 3] -> [0, 2]). Потоа, втората од двете операции ја правиме на третиот интервал, со тоа што го поместуваме во десно ([3, 5] -> [4, 6]. Со ова го покриваме целиот интервал [0, 6], па затоа одговорот е 6.

Објаснување за вториот пример: Ќе го поместиме вториот интервал во лево ([6, 7] -> [5, 6]). Откако ја извршивме оваа операција, покриени се интервалите [1, 2] и [5, 7] на бројната оска, па затоа одговорот е 1 + 2 = 3.