연산

Code Jam에서는 "연산"이라는 게임을 즐겨 한다. (아니다, 수술과는 아무 관계가 없다. 왜 그렇게 생각했는가?) 이 게임은 카드로 진행하며, 각 카드에는 기본 산술 연산(덧셈, 뺄셈, 곱셈 또는 나눗셈) $O_{i}$와 그 연산의 정수 오른쪽 피연산자 $V_{i}$가 적혀 있다. 예를 들어, 카드에는 + 0, - -2, 또는 / -4가 적혀 있을 수 있다. 피연산자는 음수이거나 0일 수도 있지만, 나눗셈 연산 카드의 피연산자가 0인 경우는 절대 없다는 점에 유의한다.

게임의 각 라운드에서는 시작 정숫값 S를 하나 정하고 C장의 카드로 이루어진 집합을 펼쳐 놓는다. 플레이어는 각 카드를 정확히 한 번씩 사용하도록 카드의 순서를 정해야 한다. 그런 다음 시작 값 S에 해당 연산들을 순서대로 적용하여 최종 결과를 얻는다.

카드에 적힌 모든 피연산자는 정수이지만, 연산은 유리수에 대해 수행된다. 예를 들어, 초깃값이 5이고 카드가 + 1, - 2, * 3, / -2라고 하자. 위에 주어진 순서대로 놓으면 최종 결과는 (5 + 1 - 2) * 3 / (-2) = -6이다. 연산자 우선순위와 관계없이 카드가 주어진 순서대로 연산을 수행한다는 점에 유의한다. 반면 - 2, / -2, + 1, * 3 순서를 선택하면 결과는 ((5 - 2) / (-2) + 1) * 3 = -3 / 2이다. 이 예의 결과가 해당 카드 집합에서 가능한 최댓값이다.

카드 집합이 주어질 때, 얻을 수 있는 최종 값의 최댓값을 구할 수 있는가? 결과는 양의 분모를 갖는 기약분수로 제시한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. -1,000 ≤ S ≤ 1,000. 모든 i에 대해 $O_{i}$는 +, -, *, / 중 하나이다. 모든 i에 대해 -1,000 ≤ $V_{i}$ ≤ 1,000. 모든 i에 대해 $O_{i}$ = /이면 $V_{i}$ ≠ 0이다.

소규모 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. 1 ≤ C ≤ 15.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ C ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 정수 S와 C가 있는 한 줄로 시작하며, 각각 게임의 시작 값과 카드 수를 나타낸다. 이어서 C개의 줄이 주어진다. 이 중 i번째 줄은 카드 한 장을 나타내며, 연산을 나타내는 문자 하나 $O_{i}$(이 문자는 +, -, *, / 중 하나이다)와 피연산자를 나타내는 정수 하나 $V_{i}$를 포함한다.

각 테스트 케이스마다 Case #x: y z를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y와 z는 y/z가 게임에서 가능한 최종 값의 최댓값이 되며, y와 z의 공약수가 1와 -1 이외에는 없고, z가 0보다 엄격히 큰 정수이다.

예제 케이스 #1에서 최적의 전략은 * 2 카드를 - 3 카드보다 먼저 사용하는 것이며, 그 결과 -1을 얻는다. 문제에서 명시한 이 값의 유일한 유리수 표현은 -1 1이다.

예제 케이스 #2는 문제 설명의 세 번째 문단에서 설명한 경우이다.

예제 케이스 #3에서는 카드를 사용하는 순서와 관계없이 같은 답을 얻는다. 답의 분자가 64비트 정수에 담기에는 너무 크다는 점에 유의한다.

예제 케이스 #4에서 얻을 수 있는 가장 큰 결과는 1이다. 한 가지 방법은 / -1, * 0, - -1이다.

예제 케이스 #5에서 답의 유효한 표현은 0 1뿐이라는 점에 유의한다. 0 2는 약분할 수 있으므로 유효하지 않다. 0 -1는 분모가 양수여야 하므로 유효하지 않다.