Again, there is a lot of input, and Python cannot process the input as fast as other languages.
One thing you can do is try
import psyco; psyco.full()
at the top of your code, and wrap the entire program in a main() function (make sure to call it at the end), like this:
import psyco; psyco.full()
def main():
[program here]
main()
For this problem, it will not help, I think. There is just too much input.