Two emerging trends of Internet applications, video traffic becoming dominant and usage-based pricing becoming prevalent, are at odds with each other. Given this conflict, is there a way for users to stay within their monthly data plans (data quotas) without suffering a noticeable degradation in video quality? In this work, we develop an online video adaptation system, called Quota Aware Video Adaptation (QAVA), that manages this tradeoff by leveraging the compressibility of videos and by predicting consumer usage behavior throughout a billing cycle. We propose the QAVA architecture and develop its main modules, including Stream Selection, User Profiling, and Video Profiling. Online algorithms are designed through dynamic programming and evaluated using real video request traces. Empirical results suggest that QAVA can provide an effective solution to the dilemma of usage-based pricing of heavy video traffic.