치킨치킨치킨
시간 제한1초메모리 제한128 MB
N명의 선호도가 주어질 때 치킨을 최대 3종류 골라 구성원별로 고른 치킨 중 최대 선호도의 합을 최대화한다.
문제
N명의 고리 회원들이 치킨을 주문하려고 합니다.
치킨은 총 M가지 종류가 있고, 회원마다 각 치킨에 대한 선호도가 있습니다. 한 사람의 만족도는 주문한 치킨 중에서 선호도가 가장 큰 값으로 정해집니다. 진수는 회원들의 만족도 합이 최대가 되도록 치킨을 주문하려고 합니다.
주문하는 치킨 종류가 많아질수록 튀기는 데 걸리는 시간도 길어지므로, 최대 세 가지 종류의 치킨만 주문하려고 합니다.
진수를 도와 만족도 합의 최댓값을 구하세요.
입력
첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30)과 치킨 종류의 수 M (3 ≤ M ≤ 30)이 주어집니다.
두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.
i+1번째 줄에는 i번째 회원의 선호도 a**i,1, a**i,2, ..., a**i,M (1 ≤ a**i,j ≤ 9)가 주어집니다.
출력
첫 번째 줄에 고리 회원들의 만족도 합의 최댓값을 출력합니다.