Informatica Online Judge

  민제의 탈옥 [2404 / 0964]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 0   Total Tried : 0


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[USACO Brian Dean]

Background

민제와 그 친구들은 체포되어서 머나먼 섬에 있는 감옥에 감금되었다. (무슨죄를 지었길래... ㅠㅠ)

그리고 머리가 좋은 민제는 탈출을 계획한다.

이 감옥은 N*K의 격자로 표현되며 각 감방(교차점)에 마다 민제를 비롯한 친구들이 한 명씩 감금되어 있다. 각 감방(교차점)을 연결하는 길마다 감시카메라가 존재한다.

민제는 시스템을 해킹하여 일부 감시카메라를 해제할 수 있지만 각 각 카메라를 해제하는데는 각각의 비용이 든다.

친구들이 모두 탈출하기 위해서는 모든 친구들이 한 곳에 모일 수 있도록 감시카메라가 해제되어야 한다. (그렇게 하면 그 위치에서 지상으로 굴을 파고 탈출할 수 있다.)

주도 면밀한 민제는 하나의 탈출 계획만으로는 안심을 할 수 없다. 따라서 민제는 최소 비용으로 모두 모일 수 있도록 카메라를 해제할 수 있는 모든 방법을 구하고자 한다. 최소비용 탈출 모든 카메라 해제 방법의 수 구하시오.

단 이 수는 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 구하시오.

Input

첫 번째 줄에 N과 K가 공백으로 구분되어 입력된다.

다음 줄부터 N줄에 걸쳐서 K-1개의 정수가 공백으로 구분되어 입력된다. 이 값은 가로로 연결된 길들에 대한 카메라 해제 비용을 의미한다.

다음 줄부터 K줄에 걸쳐서 N-1개의 정수가 공백으로 구분되어 입력된다. 이 값은 세로로 연결된 길들에 대한 카메라 해제 비용을 의미한다.

[입력값의 정의역]

2 <= N <= 30,000
2 <= K <= 6
1 <= 각 비용 값 <= 1,000,000,000

Output

문제에서 구한 모든 최소 비용의 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

IO Example

입력
4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1

출력
10

* 설명 : 위 케이스는 4*3격자로 아래와 같이 구성되어 있다.

1 1
+-----+-----+
| | |
1 | |2 | 1
| 5 | 6 |
+-----+-----+
| | |
1 | |3 | 1
| 7 | 8 |
+-----+-----+
| | |
1 | |4 | 1
| | |
+-----+-----+
1 1



이 경우에는 비용이 2, 3인 카메라를 해제하고 비용이 1인 10개의 카메라 중 9개를 해제하면 최소비용이다.

10개의 카메라 중 어떤 9개를 고르더라도 모두 최소비용이므로 경우의 수는 모두 10개이다. 따라서 답은 10이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]