TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

97.2% (70/72)

Submission's AC Ratio

42.9% (115/268)

Tags

Description

你為了預防往後幾年閃光災害上網查詢資料,滑FB滑到一半時,手機噴射出白光,將屋頂開了一個洞,你知道誰是暖化的元兇了。
站在大魔王瓦Z前,你的腳止不住的發抖,剛剛有一人路過跌倒,手上的爆米花灑了一地,瓦Z竟然就把它吃了!
「若放閃是罪,那我早被火把燒死了」瓦Z笑著說
「可是不解決你,我會愧對身為LCS會長」
你開始考慮是否別送死,想想阿公阿嬤,爸媽,滿櫃未開封的小說,未完結的獵人,寵物吉斯,還有可愛的妹妹..
「你沒有妹妹」
「今天不是你死就是我亡!」悲憤的咆哮。

身為魔法師幻想宅,你靠幻想招式攻擊.給你你和魔王的體力$W$和$B$,戰鬥方式如下:戰鬥由許多回合組成,每回合雙方各攻擊對方一次。你有$N$個招式,每次攻擊挑一招使用,消耗$A_i$ 體力,給予$D_i$傷害。大魔王瓦Z每次攻擊不消耗體力,給予固定傷害$M$。某回合結束時,若一方體力耗盡,則另一方勝利(但是和對方同歸於盡不算勝利)。試問:有沒有可能戰勝魔王呢?

Input Format

每組包含多筆測資,第一行有一個正整數$T$,表示有$T$筆測資。每筆測資第一行有3個正整數$W, B, N$,接下來的$N$行各有二個正整數$A_i, D_i$,接著最後一行有一個正整數$M$。

$A_i \le W \le 10000$
$B \le 100000$
$N \le 1000$
$D_i \le 1000$
$M \le 1000$

Output Format

對於每筆測資,若可以打敗魔王,請輸出Yes,若不可能,請輸出No。

Sample Input 1

2
10 100 1
1 30
1
20 150 2
6 50
1 10
5

Sample Output 1

Yes
No

Hints

一番苦戰,大魔王瓦Z坐倒在地上.
「我有妹妹....對....我.有妹妹.....我...不.....妹妹......我....我也想要有個妹妹啊!!」你對著瓦Z哭喊
「其實....妹妹一直都在..你身旁...只是....你不接受...妹妹...是..幻想的事實.....你這樣..還是個幻想宅嗎!」瓦Z斥道
瓦Z一番話當頭棒喝,你拾起淚水,忽然--
「歐尼醬!咦,你怎麼哭了?」

END

感謝奇片,羅琳,瓦Z,支倉

對於33%的測資,保證$N \le 100$,$W \le 1000$,$M \ge 200$

Problem Source

Subtasks

No. Testdata Range Score
1 0~1 33
2 2~5 67

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 2
5 1000 65536 262144 2