문제
X+Y+Z개의 상자가 있다. 각 상자에는 Ai개의 금 동전, Bi개의 은 동전, Ci개의 동 동전이 들어있다.
당신은 X개의 상자에서 금 동전을, Y개의 상자에서 은 동전을, Z개의 상자에서 동 동전을 꺼낼 것이다. 다만, 같은 상자에서는 오직 한 종류의 동전만 꺼낼 수 있다.
당신은 최대 몇 개의 동전을 꺼낼 수 있을까?
입력
첫 번째 줄에 정수 X, Y, Z (1 ≤ X, Y, Z, X+Y+Z ≤ 100,000) 가 주어진다.
두 번째 줄부터 X+Y+Z개의 줄에 Ai, Bi, Ci (1 ≤ Ai, Bi, Ci ≤ 10^9) 가 주어진다.
출력
첫 번째 줄에 꺼낼 수 있는 최대 동전의 수를 출력한다.
예제 #1
1 2 1
2 4 4
3 2 1
7 6 7
5 2 3
18
예제 #2
3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2
110
예제 #3
6 2 4
33189 87907 277349742
71616 46764 575306520
8801 53151 327161251
58589 4337 796697686
66854 17565 289910583
50598 35195 478112689
13919 88414 103962455
7953 69657 699253752
44255 98144 468443709
2332 42580 752437097
39752 19060 845062869
60126 74101 382963164
3093929975
출처
Atcoder
로그인해야 코드를 작성할 수 있어요.