시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB44352877.778%

문제

Bitlandijos maisto pristatymo įmonėje „Unter Valgyt” dirba du kurjeriai. Kurjeriai pradeda darbą tuo pačiu laiku – ryte (Bitlandijos laiku t = 0 minučių). Dienos metu gaunami užsakymai, apie kiekvieną kurių yra žinoma:

  • Užsakymo gavimo laikas (minutėmis);
  • Vertė, kiek kurjeris uždirbs už jo įvykdymą;
  • Laikus, kiek užtruktų kiekvienas kurjeris įvykdyti užsakymą (minutėmis). Vieno užsakymo įvykdymo laikai yra skirtingi abiems kurjeriams.

Užsakymas yra priskiriamas laisvam kurjeriui (tuo metu nevykdančiam jokio užsakymo), kuris jį įvykdytų greičiausiai. Jei tuo metu abu kurjeriai yra užimti, užsakymas dingsta, nes klientas kreipiasi į kitą įmonę.

Kurjeriai baigia dirbti, kai įvykdo visus per dieną gautus užsakymus.

Suskaičiuokite, kiek kiekvienas kurjeris uždirbs per dieną.

입력

Pirmoje eilutėje yra pateiktas užsakymų skaičius M. Kitose M eilučių duota užsakymų informacija:

  • t – užsakymo gavimo laikas minutėmis nuo darbo dienos pradžios. Visų užsakymų laikai yra skirtingi ir pateikti didėjimo tvarka.
  • v – užsakymo vertė, kurią kurjeris uždirbs jį įvykdęs.
  • z1, z2 – laikai, kurie reiškia, kad i-asis kurjeris įvykdyti šį užsakymą užtruks zi minučių. Abu vieno užsakymo laikai yra skirtingi.

출력

Vienoje eilutėje pateikite du skaičius – kiek uždirbs kiekvienas kurjeris tą dieną.

제한

  • 1 ≤ M ≤ 1000
  • 1 ≤ t1 < t2 < t3 < ... < tm ≤ 1000
  • 1 ≤ vi ≤ 1000
  • 1 ≤ zi ≤ 100

예제 입력 1

3
1 2 1 2
2 3 3 4
4 6 3 2

예제 출력 1

5 6

Gavus pirmą užsakymą abu kurjeriai laisvi, todėl jis priskiriamas pirmajam, kuris jį įvykdys per 1 minutę ir uždirbs 2 pinigus.

Antras užsakymas gaunamas už minutės. Pirmasis kurjeris jau baigė vykdyti ankstesnį užsakymą ir žada įvykdyti antrą greičiausiai (per 3 minutes), todėl jį taip pat gauną ir uždirba dar 3 pinigus.

Nors trečią užsakymą vėl greičiausiai įvykdytų pirmasis kurjeris, jis šio gauti negali, nes vis dar vykdo antrą. Trečią užsakymą gauna antrasis kurjeris.

예제 입력 2

9
1 1 2 3
2 1 3 2
3 1 2 3
4 1 3 2
5 1 2 3
6 1 3 2
7 1 4 3
8 1 3 2
9 1 3 2

예제 출력 2

4 4

Pirmą užsakymą gauna pirmasis kurjeris, antrą - antrasis. Toliau užsakymai ateina taip, kad kiekvienas kurjeris gali pradėti vykdyti naują užsakymą iš karto po ką tik vykdyto pabaigimo. Paskutinis užsakymas nebus įvykdytas, nes abu kurjeriai tuo laiku bus užimti.