TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

80.0% (8/10)

Submission's AC Ratio

26.8% (11/41)

Tags

Description

沉浸在____的歡樂不知道過了多久,當你回過神來,竟然不知不覺間被無邊無際的僵屍海團團包圍了!!!

但現在的你赤手空拳,就像睡著的小嘰一樣只能任人宰割,更不用說要保護好身邊的小蘿莉了。僵屍們一步步包圍上來,還不時發出「啊~嘶~~~」的恐怖聲音。

「喔膩醬我好害怕!!」
身邊的小蘿莉忍不住恐懼而緊緊抱住了你。
「就讓時間永遠停在這一刻吧...」
你開始這樣想,完全放棄了求生的機會...

突然間,一個神祕男子出現在你們身旁,身上只穿著一條內褲,顯現出完美的肌肉線條,只見他對你露出一個燦爛的笑容。

接著轉身大喊「比利電波!!!!!!!!!!」
一道刺眼的強光閃過,無數隻僵屍發出了驚天動地的哀嚎。當你再次睜開雙眼,就只剩下幾隻苟延殘喘要死不活求生不得求死不能的虛弱僵屍了。

神祕男子再次對你露出微笑並走過來。原來他叫作「比利」,曾經是世界第一的職業摔角手,傳說只要遇過他的對手之後都不敢再比摔角。而現在更是令僵屍聞風喪膽的專業僵屍殺手!!

(以下正題開始)

剛剛那招「比利電波」是他的其中一招必殺技,能夠瞬間殲滅無數僵屍,但只能在僵屍數量夠多的時候使用。

原來這種僵屍有個習性,當他們數量夠多時會排成一種隊伍,
構造就像一棵H層的滿支二元樹。
第一層會有一隻編號1的僵屍,每隻編號x的僵屍身後都站著一隻編號$2x$和$2x+1$的僵屍,以此類推。也就是說$1~H$層總共會有$2^ H−1$隻僵屍。
比利電波只要攻擊僵屍1,就會從1傳給2和3,2再傳給4、5,3傳給6、7,…,直到傳完H層。

不幸的是,有些僵屍能夠某種程度上的抵抗「比利電波」,他們不會被打死而且也不會把電波傳到身後。幸好有些特殊的僵屍和僵屍1有聯結,就算前面站的僵屍能抵抗電波,還是會被與1同時被電波攻擊,並繼續向後傳下去。

聽完了解說,你決定來計算這招總共能消滅多少僵屍,以作為日後對付僵屍的參考。 

Input Format

第1行有一個正整數T,接著有T筆測資。
每筆測資的第一行有兩個正整數H,N
代表這群僵屍總共有H層,有N隻特殊的僵屍
接下來N行每行有兩個數字 a,b (2≤a≤2H −1,b=0 or 1)
b=0代表編號a的僵屍能夠抵抗電波
b=1代表編號a的僵屍與僵屍1有聯結,會向後發出電波

Output Format

輸出一個正整數,代表最後能消滅多少僵屍。

Sample Input 1

2
2 0
3 1
2 0

Sample Output 1

3
4

Hints

所有測資組 : T≤10
測資組A : H≤16,N≤10
測資組B : H≤30,N≤500
測資組C : H≤50,N≤10000
測資組D : H≤63,N≤105

Problem Source

Step5

Subtasks

No. Testdata Range Score
1 0~1 10
2 2~3 20
3 4~5 30
4 6~9 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 2
3 1000 65536 262144 2
4 1000 65536 262144 3
5 1000 65536 262144 3
6 3000 65536 262144 4
7 3000 65536 262144 4
8 3000 65536 262144 4
9 3000 65536 262144 4