Dviratis

면접 대비

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

요약

비가 안 올 때만 자전거를 타는데, 아침과 저녁 모두 상황에 따라 자전거 위치가 바뀌므로, 자전거가 어디에 있는지 상태로 두고 밤에 어디에 둘지 정한다. 각 날에 자전거를 탈 수 있는지 판단하는 문제.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

Aleksas gyvena dideliame mieste. Prieš porą mėnesių, paveiktas pandemijos, jis nusprendė pakeisti gyvenimo būdą ir į darbą pradėti važinėti dviračiu. „Taip ir man sveikiau, ir planetai geriau.“ – samprotavo Aleksas.

Tačiau viskam yra ribos. Aleksas yra pasiryžęs važiuoti dviračiu tik tada, kai nelyja. Jis taip pat gali nuspręsti palikti savo dviratį darbe ir grįžti namo viešuoju transportu, jei vakare pradeda lyti. Taigi, Aleksas elgiasi taip:

Ryte, jeigu lyja arba Alekso dviratis ne namie, jis važiuoja į darbą viešuoju transportu. Priešingu atveju, jis gali važiuoti į darbą dviračiu (bet gali ir viešuoju transportu).
Vakare, jeigu lyja arba Alekso dviratis ne darbe, jis grįžta namo viešuoju transportu. Priešingu atveju, jis gali grįžti namo dviračiu (bet gali ir viešuoju transportu).

Aleksas stebi orų prognozę ir norėtų susiplanuoti savo keliones taip, kad kuo daugiau dienų jis pasinaudotų dviračiu bent vieną kartą (t. y. ryte, vakare, arba abu kartus).

Duota orų prognozė ateinančioms N dienų. Raskite, kiek daugiausiai dienų Aleksas galės važiuoti dviračiu.

입력

Pirmoje eilutėje pateiktas dienų skaičius N.

Tolesnėse N eilučių surašytos orų prognozės ateinančioms N dienų. Kiekvieną eilutę sudaro du sveikieji skaičiai ri ir vi:

ri lygus 1, jei i-osios dienos ryte nelis (galima važiuoti dviračiu), ir 0 priešingu atveju.
vi lygus 1, jei i-osios dienos vakare nelis (galima važiuoti dviračiu), ir 0 priešingu atveju.

출력

Išveskite vienintelį sveiką skaičių: kiek daugiausiai dienų Aleksas galės važiuoti dviračiu.

제한

1 ≤ N ≤ 1 000 000

힌트

Pirmąją dieną Alekso dviratis visuomet yra namie. Pasibaigus N dienų, Alekso dviratis gali būti tiek namie, tiek paliktas darbe.

예제2

예제 1
입력
```
3
1 1
0 1
0 0
```
예상 출력
```
2
```
예제 2
입력
```
7
1 1
1 0
0 1
0 1
0 1
0 0
1 1
```
예상 출력
```
4
```