시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB44516112732.732%

문제

주은이와 명진이는 사적으로 위스키를 거래하는 사이이다. 주은이는 돈도 많고 위스키를 무척 좋아해서 위스키를 가능한 한 많이 사고 싶어하고, 명진이는 위스키가 넘쳐나서 위스키를 가능한 한 많이 팔고 싶다. 하지만 주은이 자신의 사회적 평판과 품위 때문에, 한 번에 너무 많은 양의 위스키를 직거래하는 것을 꺼려 한다. 그래서 주은이는 자신의 친구를 총동원하고 명진이에게도 은밀하게 부탁하여 사설 유통망을 구축해내기로 했다. 유통망의 구조는 다음과 같다.

  • 주은이가 명진이에게 위스키를 주문한다.
  • 명진이는 가능한 한 많은 위스키를 적절하게 분배하여 명진이의 친구들에게 발송한다.
  • 명진이의 친구들은 자신의 연락망을 토대로 유통망 안에서 위스키를 주고받을 수 있다. 이들 중 몇몇은 주은이의 친구들과 연락할 수 있지만, 주은이와 직접 연락할 수는 없다.
  • 명진이의 친구들에게서 위스키를 전달받은 주은이의 친구들은 모든 위스키를 주은이에게 전달한다.

명진이는 위스키를 무한하게 보낼 수 있고, 주은이 역시 친구들로부터 받을 수 있는 위스키의 양에 제한이 없다. 하지만 명진이와 주은이의 친구들도 각자의 사회적 평판을 걱정하기 때문에 각각 한 명에게서 전달받을 수 있는 양이 정해져 있다. 예를 들어 A가 한 번에 최대 5병의 위스키를 받을 수 있다면, A는 3명의 친구들로부터 위스키를 5병씩 전달받아서 주은이에게 총 15병을 전달할 수 있지만, 1명의 친구로부터 6병을 전달받지는 못한다.

각 친구들이 한 명에게서 최대 몇 병의 위스키를 전달받을 수 있는지, 명진이의 친구들이 누구에게 연락할 수 있는지에 대한 정보가 주어졌을 때, 주은이가 한 번에 최대 몇 병의 위스키를 받을 수 있을지를 구하여라.

입력

첫째 줄에 주은이의 친구들의 수 N과 명진이의 친구들의 수 M이 주어진다. (1 ≤ N, M ≤ 100)

둘째 줄에 주은이의 친구들이 한 명으로부터 전달받을 수 있는 최대 위스키의 양을 순서대로 입력한다. 이때 주은이의 친구들은 입력된 순서대로 1부터 N까지의 번호를 배정받는다.

셋째 줄에 명진이의 친구들이 한 명으로부터 전달받을 수 있는 최대 위스키의 양을 순서대로 입력한다. 이때 명진이의 친구들은 입력된 순서대로 N+1부터 N+M까지의 번호를 배정받는다.

한 명으로부터 전달받을 수 있는 최대 위스키의 양은 10,000,000을 넘지 않는다.

넷째 줄부터 M개의 줄에 걸쳐 명진이의 친구들이 각각 연락할 수 있는 사람들의 수 K와 그 리스트가 공백으로 구분되어 주어진다. (1 ≤ K ≤ N + M - 1)

출력

첫째 줄에 주은이가 한번에 최대 몇 병의 위스키를 받을 수 있을지 출력한다.

예제 입력 1

2 2
1 1
2 3
1 1
2 1 2

예제 출력 1

3

3이 1에게 1병을, 4가 1과 2에게 1병씩 전달한 후에 1과 2가 주은이에게 위스키를 전달하면 주은이는 총 3병의 위스키를 받을 수 있다.

출처

University > 한양대학교 ERICA 캠퍼스 > 2019 HEPC > MAVEN League I번

  • 문제를 만든 사람: apwgg045
  • 문제를 다시 작성한 사람: jh05013