Slike

시간 제한1초메모리 제한1024 MB

요약

N개의 그림 나이와 M일의 계획이 주어질 때, 매일 미르코가 SM_i 이상인 그림을 최대 CM_i개 사고 그다음 슬라브코가 SS_i 이하인 그림을 최대 CS_i개 산다. 두 사람이 서로의 결과를 최소화하려 할 때 최종 구매 수를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 구간, 구현
정답자: 아직 제출이 없습니다

문제

Jedna se umjetnička galerija našla u financijskim problemima te je odlučila prodati $N$ slika koje posjeduje. Svaka slika ima svoju starost $S\_i$ – broj dana koji su prošli od kada je slika napravljena. Pravo otkupa su dobili stari kolekcionari Mirko i Slavko koji su, da bi kupovina bila zanimljivija, dogovorili sljedeća pravila.

Slike će kupovati tijekom $M$ dana. Svaki će dan u galeriju prvo doći Mirko s namjerom da kupi najviše $CM\_i$ slika starosti veće ili jednake od $SM\_i$ . Nakon što je on kupio slike koje je želio, dolazi Slavko koji želi kupiti najviše $CS\_i$ slika starosti manje ili jednake od $SS\_i$ . Obojici je cilj kupiti što više slika, a da onaj drugi pritom kupi što manje.

Ako obojica znaju unaprijed svoje i prijateljeve planove za kupovinu slika za svih $M$ dana, koliko će slika kupiti Mirko, a koliko Slavko ako obojica kupuju optimalno?

입력

U prvom su retku dva prirodna broja $N$ , $M$ ( $1 ≤ N, M ≤ 200\\,000$ ), brojevi iz teksta zadatka.

U drugom se retku nalazi $N$ prirodnih brojeva $S\_i$ ( $1 ≤ S\_i ≤ 10^9$ ) – starosti slika redom od $1$ do $N$ .

U $i$ -tom od sljedećih $M$ redaka nalaze se četiri broja $CM\_i$ , $SM\_i$ , $CS\_i$ , $SS\_i$ ( $1 ≤ CM\_i, CS\_i ≤ N$ , $1 ≤ SM\_i, SS\_i ≤ 10^9$ ), brojevi iz teksta zadatka.

출력

U prvi redak ispiši dva broja – koliko će slika kupiti Mirko, a koliko Slavko.

힌트

Opis prvog probnog primjera: Kupovina se mogla odvijati ovako: Mirko će u prvom danu kupiti slike starosti $4$ i $5$ , a Slavko će kupiti sliku starosti $1$ .

예제3

예제 1
입력
```
5 1
1 2 3 4 5
2 3 1 3
```
예상 출력
```
2 1
```

예제 2

입력

10 2
4 4 4 3 3 2 9 8 1 7
4 4 2 9
1 4 3 3

예상 출력

4 5

예제 3
입력
```
6 2
5 3 2 5 1 1
2 1 1 5
3 1 2 5
```
예상 출력
```
5 1
```