Емил многу сака да јаде колачиња од компанијата WBR. Оваа компанија нуди колачиња во три различни бои: бели, црни и розови колачиња. Емил истражил во кои N продавници во Скопје може да се најдат колачиња од компанијата WBR, и за секоја продавница тој знае точно колку бели, црни и розови колачиња има во истата.

Емил е (малку) срамежлив и не сака од една продавница да земе колачиња од две или три различни бои – туку, само од една боја. Кога тој ќе одлучи која боја колачиња да ги земе од една продавница, тој ги зема сите колачиња (во таа боја) од продавницата – бидејќи Емил е успешен програмер и за него не е проблем цената.

Емил сака да купи бели колачиња од W продавници, црни колачиња од B продавници, и розови колачиња од R продавници (W+B+R=N). Напишете програма која ќе пресмета колку најмногу вкупно колачиња може да купи Емил.

Влез

Во првиот ред се запишани четири цели броја: W, B, R и N (1 <= W, B, R, и N <= 100000). Во сите тест случаи ќе важи дека W+B+R=N. Во секој од следните N редови се запишани по три цели броја Wi, Bi и Ri (1 <= Wi, Bi, Ri <= 1000000000), кои означуваат колку бели (Wi), црни (Bi) и розови (Ri) колачиња има во i-тата продавница.

Забелешка: Во тест случаи кои носат најмалку 30% од поените, N ќе биде цел број помал или еднаков на 12. Во други тест случаи кои носат најмалку 30% од поените, N ќе биде цел број помал или еднаков на 50.

Излез

Отпечатете го бараниот максимален број на колачиња.

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

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

Примери

влез
1 1 1 3
5 4 5
1 2 5
4 3 1

излез
13

Објаснување за првиот пример: Емил може да земе 5 бели колачиња од првата продавница, 3 црни од третата продавница, и 5 розови од втората продавница (5+3+5=13).