Page not loading? Try clicking here.
Placeholder

#5680

조각사 4s 256MB

Problems

조각사 준혁이는 요즘 고민에 빠졌다. 작품을 만들기 위해서는 나무가 필요한데, 최근 발표된 정부의 친환경 정책에 따라 나무를 벤 만큼 다시 심어야 하게 되었기 때문이다.

준혁이는 조각을 하기 위한 나무를 구하기 위해 n개의 조경업체에 연락을 취했고, 각각의 업체에서는 나무를 하나 자르는 데 드는 비용과 심는데 드는 비용을 알려주었다. 이를 갖고 준혁이가 계산해 본 바로는 i번째 업체의 나무를 잘라 작품을 만든다면 m_i원을 벌 수 있고, 나무를 심는데는 p_i원이 든다. 조경업체들은 일은 많고 준혁이의 일정은 한정되어 있기 때문에 각각의 업체들은 최대 하나의 작업만 진행할 수 있다.

준혁이는 예술가이다. 예술가는 낭만은 많지만 돈은 없다. 준혁이는 현재 돈이 하나도 없다. (나무를 자르는 데 드는 비용은 작품의 값을 먼저 가불 받아 사용하기 때문에 지불할 수 있다.) 하지만, 자신의 작품을 세상에 최대한 많이 남기고 싶다. 준혁이의 낭만을 지켜주기 위해 준혁이가 빚을 지지 않고 얼마나 많은 작품을 만들 수 있을지 알려주자.


Input

첫 줄에 n (1<=n<=100,000)이 입력된다.

둘째 줄에 자연수 m_i(m_i<=10^9) n개가 공백으로 구분되어 입력된다.

마지막 줄에 자연수 p_i(p_i<=10^9) n개가 공백으로 구분되어 입력된다.

<서브태스크>

  • #1(18점) : n<=10

  • #2(82점) : 아무런 제약조건이 없음


Output

준혁이가 만들수 있는 최대 작품 개수를 출력한다.

준혁이는 예술가이기 때문에 버는 돈은 크게 신경쓰지 않는다.


Example #1

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

Example #2

4
1 2 4 2
5 6 9 7
0

Example #3

4
9 19 6 5
20 3 16 19
1

Source

SEERC 2020
You must sign in to write code.