계단 위로 상자 나르기

존은 높은 고층 빌딩의 펜트하우스로 이사한다. 그는 짐을 모두 상자에 담아 건물 지상층 입구까지 옮겨 두었다. 하지만 엘리베이터가 고장 나서 상자들을 계단으로 위층까지 날라야 한다.

다행히 존에게는 상자를 함께 나를 친구가 많다. 이들은 상자를 들었든 안 들었든 모두 같은 속도인 분당 1개 층으로 계단을 오르내린다. 그런데 계단이 너무 좁아서 두 사람이 서로 지나칠 수 없다. 그래서 이들은 다음과 같이 하기로 했다. 상자를 든 사람은 항상 위로 올라가고, 빈손인 사람은 항상 아래로 내려간다. 두 사람이 계단 어딘가에서 만나면, 아래쪽에 있는 사람(상자를 든 사람)이 위쪽에 있는 사람(빈손인 사람)에게 상자를 건넨다. 그런 다음 아래쪽 사람은 다시 내려가고 위쪽 사람은 올라간다. 상자를 건네는 데 걸리는 시간은 0이다. 누군가 지상층에 도착하면 상자 하나를 집어 들고 위로 올라가기 시작한다. 누군가 펜트하우스에 도착하면 상자를 내려놓고 다시 내려간다.

시간이 지나면 사람들은 계단 여기저기에 흩어져 있고, 어떤 사람은 상자를 들고 있으며 어떤 사람은 빈손이다. 아직 지상층에는 상자가 여러 개 남아 있다. 존은 남은 상자를 모두 위로 올리는 데 시간이 얼마나 더 걸릴지 궁금하다. 그를 도와주자!

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수가 주어진다. 이어서 각 테스트 케이스마다 다음이 주어진다.

• 첫 줄에 세 정수 $N$, $F$, $B$가 주어진다 ($1 \le N, F \le 1000$, $1 \le B \le 1000000$). 각각 사람의 수, 층수($0$은 지상층, $F$는 펜트하우스), 그리고 아직 지상층에 남아 있는 상자의 수이다.
• 이어지는 $N$개의 줄에 두 정수 $f_i$와 $b_i$가 주어진다 ($0 \le f_i \le F$, $b_i$는 0 또는 1). 각 사람이 처음 있는 층과 상자를 들고 있는지 여부이다(1이면 상자를 들고 있음, 0이면 빈손).

남은 상자를 모두 펜트하우스까지 올리는 데 걸리는 시간(분)을 한 줄에 출력한다.