<s> import sys <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> f = sys . stdin <EOL> if len ( sys . argv ) >= <NUM_LIT:2> : <EOL> fn = sys . argv [ <NUM_LIT:1> ] <EOL> if fn != '<STR_LIT:->' : <EOL> f = open ( fn ) <EOL> s = """<STR_LIT>""" <EOL> l = s . split ( '<STR_LIT:\n>' ) <EOL> T = int ( l . pop ( <NUM_LIT:0> ) ) <EOL> for _T in xrange ( T ) : <EOL> P , Q , N = map ( int , l . pop ( <NUM_LIT:0> ) . split ( ) ) <EOL> healths = [ ] <EOL> golds = [ ] <EOL> for i in xrange ( N ) : <EOL> h , g = map ( int , l . pop ( <NUM_LIT:0> ) . split ( ) ) <EOL> healths . append ( h ) <EOL> golds . append ( g ) <EOL> def num_hits_to_win ( h ) : <EOL> assert h > <NUM_LIT:0> <EOL> if P > Q : <EOL> return <NUM_LIT:1> <EOL> t = <NUM_LIT:1> <EOL> while True : <EOL> m = ( ( h - <NUM_LIT:1> ) % Q ) + <NUM_LIT:1> <EOL> if <NUM_LIT:1> <= m <= P : <EOL> return t <EOL> h -= P <EOL> t += <NUM_LIT:1> <EOL> cur = { <NUM_LIT:1> : <NUM_LIT:0> } <EOL> for i in xrange ( N ) : <EOL> next = { } <EOL> hits_needed = num_hits_to_win ( healths [ i ] ) <EOL> would_win = golds [ i ] <EOL> for shots , money in cur . iteritems ( ) : <EOL> do_nothing = ( healths [ i ] + Q - <NUM_LIT:1> ) / Q + shots <EOL> next [ do_nothing ] = max ( next . get ( do_nothing , <NUM_LIT:0> ) , money ) <EOL> health = healths [ i ] <EOL> if shots == <NUM_LIT:0> : <EOL> health -= Q <EOL> shots += <NUM_LIT:1> <EOL> if health <= <NUM_LIT:0> : <EOL> continue <EOL> tower_shots = max ( ( health - ( hits_needed - <NUM_LIT:1> ) * P - <NUM_LIT:1> ) / Q , <NUM_LIT:0> ) <EOL> next_shots = shots - hits_needed + tower_shots <EOL> if next_shots < <NUM_LIT:0> : <EOL> continue <EOL> next [ next_shots ] = max ( next . get ( next_shots , <NUM_LIT:0> ) , money + would_win ) <EOL> cur = next <EOL> best = max ( cur . itervalues ( ) ) <EOL> print "<STR_LIT>" % ( _T + <NUM_LIT:1> , best ) </s>
